結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 21:42:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 134 ms / 3,000 ms |
コード長 | 1,208 bytes |
コンパイル時間 | 2,313 ms |
コンパイル使用メモリ | 206,772 KB |
実行使用メモリ | 21,760 KB |
最終ジャッジ日時 | 2025-07-11 21:42:53 |
合計ジャッジ時間 | 5,463 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:49:32: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 49 | for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]); | ^ main.cpp:9:13: note: ‘gi’ was declared here 9 | int si,sj,gi,gj; | ^~ main.cpp:49:36: warning: ‘gj’ may be used uninitialized [-Wmaybe-uninitialized] 49 | for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]); | ^ main.cpp:9:16: note: ‘gj’ was declared here 9 | int si,sj,gi,gj; | ^~ main.cpp:20:7: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized] 20 | d[si][sj][0]=0; | ^ main.cpp:9:7: note: ‘si’ was declared here 9 | int si,sj,gi,gj; | ^~ main.cpp:20:11: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized] 20 | d[si][sj][0]=0; | ^ main.cpp:9:10: note: ‘sj’ was declared here 9 | int si,sj,gi,gj; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ int h,w,m; cin>>h>>w>>m; string s[h]; for(int i=0;i<h;i++) cin>>s[i]; vector<vector<vector<int>>> d(h,vector<vector<int>>(w,vector<int>(m+1,-1))); int si,sj,gi,gj; for(int i=0;i<h;i++) for(int j=0;j<w;j++){ if(s[i][j]=='S'){ si=i; sj=j; } if(s[i][j]=='G'){ gi=i; gj=j; } } d[si][sj][0]=0; queue<tuple<int,int,int>> Q; Q.push({si,sj,0}); int dx[]{1,0,-1,0},dy[]{0,1,0,-1}; while(!Q.empty()){ auto [i,j,k]=Q.front(); Q.pop(); for(int l=0;l<4;l++){ int ni=i+dx[l],nj=j+dy[l]; if(ni<0||ni>=h||nj<0||nj>=w) continue; if(s[ni][nj]=='#') continue; int nk=k; if('1'<=s[ni][nj]&&s[ni][nj]<='9'){ nk=s[ni][nj]-'0'; } if(d[ni][nj][nk]!=-1) continue; if('a'<=s[ni][nj]&&s[ni][nj]<='i'){ if(s[ni][nj]-'a'+1==nk){ d[ni][nj][nk]=d[i][j][k]+1; Q.push({ni,nj,nk}); } } else{ d[ni][nj][nk]=d[i][j][k]+1; Q.push({ni,nj,nk}); } } } int ans=2e9; for(int i=0;i<=m;i++) if(d[gi][gj][i]!=-1) ans=min(ans,d[gi][gj][i]); if(ans>1e9) ans=-1; cout<<ans<<endl; }