#pragma GCC optimize("O3") #include using namespace std; #define rep(i, a, n) for (int i = a; i < (int)(n); i++) using ll = long long; vector move_vec = {0, 1, 0, -1, 0}; int main() { int h, w, m; cin >> h >> w >> m; vector> grid(h, vector(w, '?')); int startx = -1, starty = -1, goalx = -1, goaly = -1; rep(i, 0, h) { string s; cin >> s; rep(j, 0, w) { grid[i][j] = s[j]; if (s[j] == 'S') { startx = i, starty = j; } else if (s[j] == 'G') { goalx = i, goaly = j; } } } vector>> bfs(h, vector>(w, vector(10, INT_MAX))); bfs[startx][starty][0] = 0; queue> q; q.push({startx, starty, 0}); while (!q.empty()) { auto [x, y, key] = q.front(); if (x == goalx && y == goaly) { break; } q.pop(); rep(d, 0, 4) { int nx = x + move_vec[d], ny = y + move_vec[d + 1]; if (nx < 0 || h <= nx || ny < 0 || w <= ny || grid[nx][ny] == '#') { continue; } if (grid[nx][ny] == 'G') { bfs[nx][ny][key] = min(bfs[x][y][key], bfs[nx][ny][key]); q.push({nx, ny, key}); } if (grid[nx][ny] == '.') { if (bfs[nx][ny][key] > bfs[x][y][key] + 1) { bfs[nx][ny][key] = bfs[x][y][key] + 1; q.push({nx, ny, key}); } } else if ('0' <= grid[nx][ny] && grid[nx][ny] <= '9') { int new_key = grid[nx][ny] - '0'; if (bfs[nx][ny][new_key] > bfs[x][y][key] + 1) { bfs[nx][ny][new_key] = bfs[x][y][key] + 1; q.push({nx, ny, new_key}); } } else { int match_key = grid[nx][ny] - 'a' + 1; if (key != match_key) { continue; } if (bfs[nx][ny][match_key] > bfs[x][y][key] + 1) { bfs[nx][ny][match_key] = bfs[x][y][key] + 1; q.push({nx, ny, match_key}); } } } } int ans = INT_MAX; rep(i, 0, 10) { ans = min(ans, bfs[goalx][goaly][i]); } cout << (ans == INT_MAX ? -1 : ans + 1) << endl; }