結果

問題 No.3199 Key-Door Grid
ユーザー jiangxinyang
提出日時 2025-07-11 21:45:00
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 103 ms / 3,000 ms
コード長 1,730 bytes
コンパイル時間 2,282 ms
コンパイル使用メモリ 200,824 KB
実行使用メモリ 13,976 KB
最終ジャッジ日時 2025-07-11 21:45:22
合計ジャッジ時間 4,594 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:30:56: warning: iteration 10 invokes undefined behavior [-Waggressive-loop-optimizations]
   30 |             for (int k = 0; k <= 10; k++) dis[i][j][k] = -1;
      |                                           ~~~~~~~~~~~~~^~~~
main.cpp:30:31: note: within this loop
   30 |             for (int k = 0; k <= 10; k++) dis[i][j][k] = -1;
      |                             ~~^~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 200005;
const int INF = 0x3f3f3f3f;
struct Node {
    int x, y, k;
};
int dis[505][505][10];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<string> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int sx = -1, sy = -1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'S') {
                sx = i, sy = j;
                break;
            }
        }
        if (sx != -1) break;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k <= 10; k++) dis[i][j][k] = -1;
        }
    }
    queue<Node> q;
    dis[sx][sy][0] = 0;
    q.push({sx, sy, 0});
    auto inb = [&](int r, int c) {
        return (0 <= r && r < n && 0 <= c && c < m);
    };
    int ans = -1;
    while (!q.empty()) {
        Node u = q.front();
        q.pop();
        int d = dis[u.x][u.y][u.k];
        if (a[u.x][u.y] == 'G') {
            ans = d;
            break;
        }
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if (!(nx >= 0 && nx < n && ny >= 0 && ny < m)) continue;
            if (a[nx][ny] == '#') continue;
            int k = u.k;
            if (a[nx][ny] >= 'a' && a[nx][ny] <= 'i' && u.k != a[nx][ny] - 'a' + 1) continue;
            if (a[nx][ny] >= '1' && a[nx][ny] <= '9') k = a[nx][ny] - '1' + 1;
            if (dis[nx][ny][k] == -1) {
                dis[nx][ny][k] = d + 1;
                q.push({nx, ny, k});
            }
        }
    }
    cout << ans << "\n";
    return 0;
}
0