結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-08-14 18:33:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 3,000 ms |
コード長 | 1,747 bytes |
コンパイル時間 | 1,010 ms |
コンパイル使用メモリ | 110,024 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2025-08-14 18:33:28 |
合計ジャッジ時間 | 5,120 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:15:17: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized] 15 | int sx, sy, gx, gy; | ^~ main.cpp:15:21: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized] 15 | int sx, sy, gx, gy; | ^~ main.cpp:35:20: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized] 35 | dis[sx][sy][0] = 0; | ~~~~~~~~~~~~~~~^~~ main.cpp:15:9: note: ‘sx’ was declared here 15 | int sx, sy, gx, gy; | ^~ main.cpp:35:20: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized] 35 | dis[sx][sy][0] = 0; | ~~~~~~~~~~~~~~~^~~ main.cpp:15:13: note: ‘sy’ was declared here 15 | int sx, sy, gx, gy; | ^~
ソースコード
#include <iostream> #include <tuple> #include <queue> #include <algorithm> #include <cctype> using namespace std; using t3i = tuple<int, int, int>; using qt3i = queue<t3i>; int main() { int n, m, k; cin >> n >> m >> k; int sx, sy, gx, gy; char s[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> s[i][j]; if (s[i][j] == 'S') { sx = i; sy = j; } else if (s[i][j] == 'G') { gx = i; gy = j; } } } int dis[n][m][k+1]; fill(dis[0][0], dis[n][0], -1); qt3i q; q.emplace(sx, sy, 0); dis[sx][sy][0] = 0; constexpr int dx[4] = {0, 1, 0, -1}; constexpr int dy[4] = {1, 0, -1, 0}; while (!q.empty()) { auto [x, y, key] = q.front(); q.pop(); for (int z = 0; z < 4; z++) { int nx = x + dx[z], ny = y + dy[z], nkey = key; if (nx < 0 || nx >= n || ny < 0 || ny >= m || s[nx][ny] == '#') { continue; } if (isdigit(s[nx][ny])) { nkey = s[nx][ny] - '0'; } if (islower(s[nx][ny])) { if (nkey != s[nx][ny] - 'a' + 1) { continue; } } if (dis[nx][ny][nkey] == -1) { dis[nx][ny][nkey] = dis[x][y][key] + 1; q.emplace(nx, ny, nkey); } } } int ans = -1; for (int i = 0; i <= k; i++) { if (dis[gx][gy][i] != -1) { if (ans == -1 || dis[gx][gy][i] < ans) { ans = dis[gx][gy][i]; } } } cout << ans << endl; return 0; }