#include using namespace std; // #include // using namespace atcoder; // using mint = modint998244353; using ll = long long; #define fix(x) fixed << setprecision(x) #define rep(i, n) for(int i = 0; i < n; ++i) #define all(x) (x).begin(),(x).end() templatebool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;} templatebool chmax(T&a, const T&b){if(a> h >> w >> m; vector s(h); int sh = -1, sw = -1, gh = -1, gw = -1; rep(i,h){ cin >> s[i]; rep(j,w){ if(s[i][j]=='S') sh = i, sw = j; if(s[i][j]=='G') gh = i, gw = j; } } vector dist(h,vector(w,vector(m+1,INF))); dist[sh][sw][m] = 0; queue> que; que.emplace(sh,sw,m); while(que.size()){ auto [p,q,x] = que.front(); que.pop(); rep(i,4){ int np = p+H[i], nq = q+W[i]; if(np<0 || np>=h || nq<0 || nq>=w || s[np][nq]=='#') continue; if(s[np][nq]>='a' && s[np][nq]<='i' && s[np][nq]-'a'!=x) continue; int y = x; if(s[np][nq]>='1' && s[np][nq]<='9') y = s[np][nq] - '1'; if(chmin(dist[np][nq][y], dist[p][q][x]+1)) que.emplace(np,nq,y); } } int ans = INF; rep(i,m+1) chmin(ans, dist[gh][gw][i]); if(ans==INF) ans = -1; cout << ans << '\n'; return 0; }