結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:35:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 3,000 ms |
コード長 | 2,201 bytes |
コンパイル時間 | 3,969 ms |
コンパイル使用メモリ | 264,200 KB |
実行使用メモリ | 33,408 KB |
最終ジャッジ日時 | 2025-07-11 21:35:24 |
合計ジャッジ時間 | 7,110 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include "atcoder/modint.hpp" #include <bits/stdc++.h> #include <atcoder/all> 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<i64, i64>; using el = tuple<i64, i64, i64>; 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<string> s(h); for (i64 i = 0; i < h; i++) cin >> s[i]; vector dp(h, vector(w, vector(m + 1, i64(1e18)))); queue<el> 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"; } }