結果

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

ソースコード

diff # 

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