結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー YY-otter
提出日時 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;
      |                                   ^~~~~~

ソースコード

diff # 

#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;
}
0