#include "atcoder/modint.hpp" #include #include using namespace std; using i32 = int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using f64 = long double; using p2 = pair; using el = tuple; using mint = atcoder::modint1000000007; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } i64 pow(i64 x, i64 n, i64 m) { i64 res = 1; i64 t = x % m; while (n > 0) { if (n & 1) { res = res * t % m; } t = t * t % m; n >>= 1; } return res; } void _main() { i64 h, w, m; cin >> h >> w >> m; vector s(h); for (i64 i = 0; i < h; i++) cin >> s[i]; vector dp(h, vector(w, vector(m + 1, i64(1e18)))); queue que; for(i64 i = 0; i < h; i++) { for (i64 j = 0; j < w; j++) { if (s[i][j] != 'S') continue; dp[i][j][0] = 0; que.push({i, j, 0}); } } while (!que.empty()) { auto [i, j, k] = que.front(); que.pop(); i64 nxt[5] = {0, 1, 0, -1, 0}; for (i64 p = 0; p < 4; p++) { i64 ni = i + nxt[p], nj = j + nxt[p + 1]; if (ni < 0 || nj < 0 || ni >= h || nj >= w || s[ni][nj] == '#') continue; if ('a' <= s[ni][nj] && s[ni][nj] <= 'z') { i64 id = s[ni][nj] - 'a' + 1; assert(id <= m); if (id != k) continue; if (dp[ni][nj][k] > dp[i][j][k] + 1) { dp[ni][nj][k] = dp[i][j][k] + 1; que.push({ni, nj, k}); } } else if ('1' <= s[ni][nj] && s[ni][nj] <= '9') { i64 nk = s[ni][nj] - '0'; assert(nk <= m); if (dp[ni][nj][nk] > dp[i][j][k] + 1) { dp[ni][nj][nk] = dp[i][j][k] + 1; que.push({ni, nj, nk}); } } else { if (dp[ni][nj][k] > dp[i][j][k] + 1) { dp[ni][nj][k] = dp[i][j][k] + 1; que.push({ni, nj, k}); } } } } i64 ans = 1e18; for (i64 i = 0; i < h; i++) { for (i64 j = 0; j < w; j++) { if (s[i][j] != 'G') continue; for (i64 k = 0; k <= m; k++) { ans = min(ans, dp[i][j][k]); } } } if (ans == 1e18) { cout << "-1\n"; } else { cout << ans << "\n"; } }