結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-01 17:56:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 3,000 ms |
コード長 | 2,036 bytes |
コンパイル時間 | 1,181 ms |
コンパイル使用メモリ | 115,632 KB |
実行使用メモリ | 21,504 KB |
最終ジャッジ日時 | 2025-07-11 05:02:13 |
合計ジャッジ時間 | 4,851 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:34:11: warning: ‘start_r’ may be used uninitialized [-Wmaybe-uninitialized] 34 | q.push({start_r, start_c, 0}); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~ main.cpp:21:9: note: ‘start_r’ was declared here 21 | int start_r, start_c, goal_r, goal_c; | ^~~~~~~ main.cpp:34:11: warning: ‘start_c’ may be used uninitialized [-Wmaybe-uninitialized] 34 | q.push({start_r, start_c, 0}); | ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~ main.cpp:21:18: note: ‘start_c’ was declared here 21 | int start_r, start_c, goal_r, goal_c; | ^~~~~~~ main.cpp:70:40: warning: ‘goal_r’ may be used uninitialized [-Wmaybe-uninitialized] 70 | ans = std::min(ans, dist[goal_r][goal_c][k]); | ^ main.cpp:21:27: note: ‘goal_r’ was declared here 21 | int start_r, start_c, goal_r, goal_c; | ^~~~~~ main.cpp:70:48: warning: ‘goal_c’ may be used uninitialized [-Wmaybe-uninitialized] 70 | ans = std::min(ans, dist[goal_r][goal_c][k]); | ^ main.cpp:21:35: note: ‘goal_c’ was declared here 21 | int start_r, start_c, goal_r, goal_c; | ^~~~~~
ソースコード
#include <iostream> #include <vector> #include <string> #include <queue> #include <tuple> #include <algorithm> #include <cctype> const int INF = 1e9; struct State { int r, c, key; }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int H, W, M; std::cin >> H >> W >> M; std::vector<std::string> grid(H); int start_r, start_c, goal_r, goal_c; for (int i = 0; i < H; ++i) { std::cin >> grid[i]; for (int j = 0; j < W; ++j) { if (grid[i][j] == 'S') { start_r = i; start_c = j; } if (grid[i][j] == 'G') { goal_r = i; goal_c = j; } } } std::vector<std::vector<std::vector<int>>> dist(H, std::vector<std::vector<int>>(W, std::vector<int>(M + 1, INF))); std::queue<State> q; dist[start_r][start_c][0] = 0; q.push({start_r, start_c, 0}); int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; while (!q.empty()) { auto [r, c, key] = q.front(); q.pop(); if (dist[r][c][key] > dist[r][c][key]) continue; // 既に短い経路が見つかっている for (int i = 0; i < 4; ++i) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr < 0 || nr >= H || nc < 0 || nc >= W || grid[nr][nc] == '#') continue; char cell = grid[nr][nc]; // 扉のチェック if (islower(cell) && (cell - 'a' + 1) != key) continue; // 次の鍵の状態 int next_key = key; if (isdigit(cell)) { next_key = cell - '0'; } if (dist[r][c][key] + 1 < dist[nr][nc][next_key]) { dist[nr][nc][next_key] = dist[r][c][key] + 1; q.push({nr, nc, next_key}); } } } int ans = INF; for (int k = 0; k <= M; ++k) { ans = std::min(ans, dist[goal_r][goal_c][k]); } if (ans == INF) std::cout << -1 << std::endl; else std::cout << ans << std::endl; return 0; }