結果

問題 No.3199 Key-Door Grid
ユーザー Hyoka7
提出日時 2025-07-12 00:14:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,657 bytes
コンパイル時間 3,022 ms
コンパイル使用メモリ 231,104 KB
実行使用メモリ 21,504 KB
最終ジャッジ日時 2025-07-12 00:15:05
合計ジャッジ時間 6,859 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < (int)(n); i++)
using ll = long long;

vector<int> move_vec = {0, 1, 0, -1, 0};

int main()
{
    int h, w, m;
    cin >> h >> w >> m;
    vector<vector<char>> grid(h, vector<char>(w, '?'));
    int startx = -1, starty = -1, goalx = -1, goaly = -1;
    rep(i, 0, h)
    {
        string s;
        cin >> s;
        rep(j, 0, w)
        {
            grid[i][j] = s[j];
            if (s[j] == 'S')
            {
                startx = i, starty = j;
            }
            else if (s[j] == 'G')
            {
                goalx = i, goaly = j;
            }
        }
    }
    vector<vector<vector<int>>> bfs(h, vector<vector<int>>(w, vector<int>(10, INT_MAX)));
    bfs[startx][starty][0] = 0;
    queue<tuple<int, int, int>> q;
    q.push({startx, starty, 0});
    while (!q.empty())
    {
        auto [x, y, key] = q.front();
        if (x == goalx && y == goaly)
        {
            break;
        }
        q.pop();
        rep(d, 0, 4)
        {
            int nx = x + move_vec[d], ny = y + move_vec[d + 1];
            if (nx < 0 || h <= nx || ny < 0 || w <= ny || grid[nx][ny] == '#')
            {
                continue;
            }
            if (grid[nx][ny] == 'G')
            {
                bfs[nx][ny][key] = min(bfs[x][y][key], bfs[nx][ny][key]);
                q.push({nx, ny, key});
            }
            if (grid[nx][ny] == '.')
            {
                if (bfs[nx][ny][key] > bfs[x][y][key] + 1)
                {
                    bfs[nx][ny][key] = bfs[x][y][key] + 1;
                    q.push({nx, ny, key});
                }
            }
            else if ('0' <= grid[nx][ny] && grid[nx][ny] <= '9')
            {
                int new_key = grid[nx][ny] - '0';
                if (bfs[nx][ny][new_key] > bfs[x][y][key] + 1)
                {
                    bfs[nx][ny][new_key] = bfs[x][y][key] + 1;
                    q.push({nx, ny, new_key});
                }
            }
            else
            {
                int match_key = grid[nx][ny] - 'a' + 1;
                if (key != match_key)
                {
                    continue;
                }
                if (bfs[nx][ny][match_key] > bfs[x][y][key] + 1)
                {
                    bfs[nx][ny][match_key] = bfs[x][y][key] + 1;
                    q.push({nx, ny, match_key});
                }
            }
        }
    }
    int ans = INT_MAX;
    rep(i, 0, 10)
    {
        ans = min(ans, bfs[goalx][goaly][i]);
    }
    cout << (ans == INT_MAX ? -1 : ans + 1) << endl;
}
0