結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 21:32:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 167 ms / 3,000 ms |
コード長 | 1,471 bytes |
コンパイル時間 | 3,108 ms |
コンパイル使用メモリ | 290,716 KB |
実行使用メモリ | 33,408 KB |
最終ジャッジ日時 | 2025-07-11 21:32:55 |
合計ジャッジ時間 | 6,779 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:27:10: warning: ‘SY’ may be used uninitialized [-Wmaybe-uninitialized] 27 | DP[SY][SX][0]=0; | ^ main.cpp:12:8: note: ‘SY’ was declared here 12 | ll SY,SX,GY,GX; | ^~ main.cpp:27:14: warning: ‘SX’ may be used uninitialized [-Wmaybe-uninitialized] 27 | DP[SY][SX][0]=0; | ^ main.cpp:12:11: note: ‘SX’ was declared here 12 | ll SY,SX,GY,GX; | ^~ main.cpp:54:41: warning: ‘GY’ may be used uninitialized [-Wmaybe-uninitialized] 54 | for(int i=0;i<10;i++)an=min(an,DP[GY][GX][i]); | ^ main.cpp:12:14: note: ‘GY’ was declared here 12 | ll SY,SX,GY,GX; | ^~ main.cpp:54:45: warning: ‘GX’ may be used uninitialized [-Wmaybe-uninitialized] 54 | for(int i=0;i<10;i++)an=min(an,DP[GY][GX][i]); | ^ main.cpp:12:17: note: ‘GX’ was declared here 12 | ll SY,SX,GY,GX; | ^~
ソースコード
#include<bits/stdc++.h> using namespace std; using ll =long long; void solve(){ ll H,W,M; cin>>H>>W>>M; vector<string> B(H); ll SY,SX,GY,GX; for(int i=0;i<H;i++){ cin>>B[i]; for(int j=0;j<W;j++){ if(B[i][j]=='S'){ SY=i; SX=j; } if(B[i][j]=='G'){ GY=i; GX=j; } } } vector<vector<vector<ll>>> DP(H,vector<vector<ll>>(W,vector<ll>(10,1e18))); DP[SY][SX][0]=0; queue<array<ll,3>> Q; Q.push({SY,SX,0}); vector<ll> nd={0,1,0,-1,0}; while(!Q.empty()){ auto [y,x,k]=Q.front(); Q.pop(); for(int d=0;d<4;d++){ ll ny=y+nd[d]; ll nx=x+nd[d+1]; ll nk=k; if(ny<0||nx<0||ny>=H||nx>=W)continue; if(B[ny][nx]=='#')continue; if('a'<=B[ny][nx]&&B[ny][nx]<='z'){ if(B[ny][nx]-'a'+1!=k)continue; } if('1'<=B[ny][nx]&&B[ny][nx]<='9'){ nk=B[ny][nx]-'0'; } if(DP[ny][nx][nk]>DP[y][x][k]+1){ DP[ny][nx][nk]=DP[y][x][k]+1; Q.push({ny,nx,nk}); } } } ll an=1e18; for(int i=0;i<10;i++)an=min(an,DP[GY][GX][i]); cout<<(an<1e17?an:-1)<<endl; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int T=1; // cin>>T; while(T--)solve(); }