結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー iastm
提出日時 2025-07-12 02:58:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 89 ms / 3,000 ms
コード長 1,640 bytes
コンパイル時間 1,389 ms
コンパイル使用メモリ 106,712 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-12 02:58:51
合計ジャッジ時間 4,019 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:29:15: warning: ‘s_i’ may be used uninitialized [-Wmaybe-uninitialized]
   29 |     queue.push({s_i, s_j, 0, 0});
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:14:9: note: ‘s_i’ was declared here
   14 |     int s_i, s_j;
      |         ^~~
main.cpp:29:15: warning: ‘s_j’ may be used uninitialized [-Wmaybe-uninitialized]
   29 |     queue.push({s_i, s_j, 0, 0});
      |     ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:14:14: note: ‘s_j’ was declared here
   14 |     int s_i, s_j;
      |              ^~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <array>
#include <queue>

constexpr int di[] = {-1, 1, 0, 0}, dj[] = {0, 0, -1, 1};

int main() {
    int H, W, M;
    std::cin >> H >> W >> M;

    std::vector<std::string> grid(H);
    for (auto &row : grid) std::cin >> row;
    int s_i, s_j;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == 'S') {
                s_i = i;
                s_j = j;
            }
        }
    }

    auto is_legal = [&](const int &i, const int &j) {
        return 0 <= i && i < H && 0 <= j && j < W && grid[i][j] != '#';
    };

    std::queue<std::array<int, 4>> queue;
    queue.push({s_i, s_j, 0, 0});
    std::vector<std::vector<std::vector<bool>>> visited(10, std::vector<std::vector<bool>>(H, std::vector<bool>(W, false)));
    visited[0][s_i][s_j] = true;

    while (!queue.empty()) {
        int i = queue.front()[0];
        int j = queue.front()[1];
        int d = queue.front()[2];
        int k = queue.front()[3];
        queue.pop();
        if (grid[i][j] == 'G') {
            std::cout << d << std::endl;
            return 0;
        }
        if ('1' <= grid[i][j] && grid[i][j] <= '9') k = grid[i][j] - '0';
        for (int rot = 0; rot < 4; rot++) {
            int ni = i + di[rot], nj = j + dj[rot];
            if (!is_legal(ni, nj)) continue;
            if ('a' <= grid[ni][nj] && grid[ni][nj] <= 'i' && k - 1 != grid[ni][nj] - 'a') continue;
            if (visited[k][ni][nj]) continue;
            visited[k][ni][nj] = true;
            queue.push({ni, nj, d + 1, k});
        }
    }
    std::cout << -1 << std::endl;
}
0