#include #include #include #include namespace mp = boost::multiprecision; using Bint = mp::cpp_int; using namespace std; using namespace atcoder; #define rep(i, n) for(int i=0;i<(n);++i) #define rep1(i, n) for(int i=1;i<=(n);i++) #define ll long long using mint = modint998244353; using P = pair; using lb = long double; using T = tuple; #ifdef LOCAL # include # define dbg(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define dbg(...) (static_cast(0)) #endif int main() { int h, w, m; cin >> h >> w >> m; vector s(h); rep(i,h) cin >> s[i]; const int INF = 1e9; vector>> dist(h, vector>(w, vector(m+1, INF))); queue> q; rep(i,h)rep(j,w) { if(s[i][j]=='S') { dist[i][j][0] = 0; q.emplace(i,j,0); } } vector di = {0, -1, 0, 1}; vector dj = {-1, 0, 1, 0}; while(!q.empty()) { auto [i,j,k] = q.front();q.pop(); dbg(i,j,k); rep(d,4) { int ni = i + di[d]; int nj = j + dj[d]; int nk = k; if(ni<0 || ni>=h || nj<0 || nj>=w) continue; if(s[ni][nj]=='#') continue; if(s[ni][nj]=='.' || s[ni][nj]=='G' || s[ni][nj]=='S') { } else if(s[ni][nj]>='1' && s[ni][nj]<='9') { nk = s[ni][nj] - '0'; } else{ if(s[ni][nj]-'a'!=k-1) continue; } if(dist[ni][nj][nk]>dist[i][j][k]+1) { dbg(nk,s[ni][nj]); dist[ni][nj][nk] = dist[i][j][k]+1; q.emplace(ni,nj,nk); } } } int ans = INF; rep(i,h)rep(j,w) { if(s[i][j]=='G') { rep(k,m+1) ans = min(ans, dist[i][j][k]); } } if(ans==INF) ans = -1; cout << ans << endl; return 0; }