結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー ルク
提出日時 2025-07-11 21:45:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,380 bytes
コンパイル時間 848 ms
コンパイル使用メモリ 88,572 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 21:45:45
合計ジャッジ時間 16,469 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <string>
using namespace std;

int main() {
    int h, w, m;
    cin >> h >> w >> m;
    vector<string> mp(h);
    for (int i = 0; i < h; ++i) {
        cin >> mp[i];
    }

    int sx = 0, sy = 0, gx = 0, gy = 0;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (mp[i][j] == 'S') {
                sx = i;
                sy = j;
                mp[i][j] = '.';
            } else if (mp[i][j] == 'G') {
                gx = i;
                gy = j;
                mp[i][j] = '.';
            }
        }
    }

    queue<tuple<int, int, int, int>> que;  // (x, y, key, dist)
    que.emplace(sx, sy, 0, 0);

    vector<vector<pair<int, int>>> visited(h, vector<pair<int, int>>(w, {-1, 0}));
    visited[sx][sy] = {0, 0};

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    while (!que.empty()) {
        auto [x, y, key, dist] = que.front();
        que.pop();
        if (x == gx && y == gy) {
            cout << dist << endl;
            return 0;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            char ch = mp[nx][ny];
            if (ch == '#') continue;

            if (ch == '.') {
                if (visited[nx][ny].first != key && visited[nx][ny].second < dist + 1) {
                    visited[nx][ny] = {key, dist + 1};
                    que.emplace(nx, ny, key, dist + 1);
                }
            } else if ('1' <= ch && ch <= '9' && ch - '0' <= m) {
                int new_key = ch - '0';
                if (visited[nx][ny].first != new_key && visited[nx][ny].second < dist + 1) {
                    visited[nx][ny] = {new_key, dist + 1};
                    que.emplace(nx, ny, new_key, dist + 1);
                }
            } else if ('a' <= ch && ch < 'a' + m) {
                if (key == 0) continue;
                if (key == ch - 'a' + 1) {
                    if (visited[nx][ny].first != key && visited[nx][ny].second < dist + 1) {
                        visited[nx][ny] = {key, dist + 1};
                        que.emplace(nx, ny, key, dist + 1);
                    }
                }
            }
        }
    }
    cout << -1 << endl;
    return 0;
}
0