結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー cled0328
提出日時 2025-07-11 21:46:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 121 ms / 3,000 ms
コード長 1,195 bytes
コンパイル時間 2,147 ms
コンパイル使用メモリ 211,140 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2025-07-11 21:46:42
合計ジャッジ時間 4,555 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int h,w,m;cin>>h>>w>>m;
    vector<string> s(h);
    for(int i=0;i<h;i++)cin>>s[i];
    int inf=h*w*(m+1);
    vector<vector<vector<int>>> dis(m+1,vector<vector<int>>(h,vector<int>(w,inf)));
    queue<tuple<int,int,int>> bfs;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(s[i][j]=='S'){
                dis[0][i][j]=0;
                bfs.push({0,i,j});
            }
        }
    }
    int ans=inf;
    while(!bfs.empty()){
        auto [key,x,y]=bfs.front();bfs.pop();
        if(s[x][y]=='G'){
            ans=dis[key][x][y];
            break;
        }
        const int d[5]={0,1,0,-1};
        for(int i=0;i<4;i++){
            int nx=x+d[i],ny=y+d[i+1];
            if(nx<0||nx>=h||ny<0||ny>=w)continue;
            if(s[nx][ny]=='#')continue;
            if(s[nx][ny]>='a'&&s[nx][ny]<='i'&&s[nx][ny]-'a'!=key-1)continue;
            int nkey=key;
            if(s[nx][ny]>='1'&&s[nx][ny]<='9')nkey=s[nx][ny]-'0';
            if(dis[nkey][nx][ny]!=inf)continue;
            dis[nkey][nx][ny]=dis[key][x][y]+1;
            bfs.push({nkey,nx,ny});
        }
    }
    cout<<(ans==inf?-1:ans)<<"\n";
}
0