結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 21:36:41 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 3,000 ms |
コード長 | 1,119 bytes |
コンパイル時間 | 3,488 ms |
コンパイル使用メモリ | 286,328 KB |
実行使用メモリ | 21,632 KB |
最終ジャッジ日時 | 2025-07-11 21:36:49 |
合計ジャッジ時間 | 6,962 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; int main(){ int h,w,m; cin>>h>>w>>m; vector<string> s(h); for(int i=0;i<h;i++)cin>>s[i]; vector<vector<vector<int>>> dist(h,vector<vector<int>>(w,vector<int>(10,1e9))); queue<pair<int,int>> bfs; for(int i=0;i<h;i++)for(int j=0;j<w;j++){ if(s[i][j]=='S'){ bfs.push(make_pair(i*w+j,0)); dist[i][j][0]=0; } } int dx[]={1,0,-1,0},dy[]={0,1,0,-1}; while(!bfs.empty()){ int x=bfs.front().first/w,y=bfs.front().first%w,key=bfs.front().second; bfs.pop(); for(int i=0;i<4;i++){ int nx=x+dx[i],ny=y+dy[i]; if(nx<0||nx>=h||ny<0||ny>=w||s[nx][ny]=='#')continue; int nkey=key; if('1'<=s[nx][ny]&&s[nx][ny]<='9')nkey=s[nx][ny]-'0'; if(dist[nx][ny][nkey]!=1e9)continue; if('a'<=s[nx][ny]&&s[nx][ny]<='i'&&'a'+(nkey-1)!=s[nx][ny])continue; bfs.push(make_pair(nx*w+ny,nkey)); dist[nx][ny][nkey]=dist[x][y][key]+1; } } int ans=-1; for(int i=0;i<h;i++)for(int j=0;j<w;j++){ if(s[i][j]=='G'){ int res=1e9; for(int k=0;k<10;k++)res=min(res,dist[i][j][k]); if(res!=1e9)ans=res; } } cout<<ans<<endl; }