#include using namespace std; #define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x, y) CPP_CAT_I(x, y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x, y) x##y #define ASSERT(expr...) assert((expr)) using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; // }}} constexpr i64 INF = 1'010'000'000'000'000'017LL; constexpr i64 MOD = 998244353LL; constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846; #define M5 100007 #define M9 1000000000 #define F first #define S second // util {{{ #define FOR(i, start, end) for (i64 i = (start), CPP_CAT(i, xxxx_end) = (end); i < CPP_CAT(i, xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() #define ll long long int #define VI vector #define VVI vector #define ISD true #define debug(x) \ if (ISD) \ cout << #x << ": " << x << endl template > bool chmax(T &xmax, const U &x, Comp comp = {}) { if (comp(xmax, x)) { xmax = x; return true; } return false; } template > bool chmin(T &xmin, const U &x, Comp comp = {}) { if (comp(x, xmin)) { xmin = x; return true; } return false; } int main() { ll H, W, M; cin >> H >> W >> M; vector S(H); REP(i, H) cin >> S[i]; int sx, sy; int gx, gy; REP(i, H) REP(j, W) { if (S[i][j] == 'S') { sx = i; sy = j; } if (S[i][j] == 'G') { gx = i; gy = j; } } using P = tuple; vector d(H, VVI(W, VI(10, INF))); queue

que; que.push({sx, sy, 0}); // sから探索する d[sx][sy][0] = 0; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; while (que.size() != 0) { // 幅優先探索 P state = que.front(); // 現在の状態 que.pop(); int x = get<0>(state); int y = get<1>(state); int t = get<2>(state); REP(k, 4) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || ny < 0 || nx >= H || ny >= W || S[nx][ny] == '#') continue; int nt = t; if ('1' <= S[nx][ny] && S[nx][ny] <= '9') { nt = S[nx][ny] - '0'; } if ('a' <= S[nx][ny] && S[nx][ny] <= 'z' && S[nx][ny] - 'a' + 1 != t) { continue; } if (d[nx][ny][nt] != INF) { continue; } d[nx][ny][nt] = d[x][y][t] + 1; que.push({nx, ny, nt}); } } ll ans = INF; REP(i, 10) { chmin(ans, d[gx][gy][i]); } if (ans == INF) { cout << -1 << endl; } else { cout << ans << endl; } }