結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:31:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 331 ms / 3,000 ms |
コード長 | 1,245 bytes |
コンパイル時間 | 4,795 ms |
コンパイル使用メモリ | 259,848 KB |
実行使用メモリ | 21,888 KB |
最終ジャッジ日時 | 2025-07-11 21:31:30 |
合計ジャッジ時間 | 8,923 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:31:15: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized] 31 | Q.push({sx,sy,m}); | ~~~~~~^~~~~~~~~~~ main.cpp:18:13: note: ‘sx’ was declared here 18 | int sx,sy,gx,gy; | ^~ main.cpp:31:15: warning: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized] 31 | Q.push({sx,sy,m}); | ~~~~~~^~~~~~~~~~~ main.cpp:18:16: note: ‘sy’ was declared here 18 | int sx,sy,gx,gy; | ^~ main.cpp:57:36: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized] 57 | ans = min(ans, d[gx][gy][i]); | ^ main.cpp:18:19: note: ‘gx’ was declared here 18 | int sx,sy,gx,gy; | ^~ main.cpp:57:40: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized] 57 | ans = min(ans, d[gx][gy][i]); | ^ main.cpp:18:22: note: ‘gy’ was declared here 18 | int sx,sy,gx,gy; | ^~
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint998244353; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000005 #define Inf64 4000000000000000001LL int main(){ int h,w,m; cin>>h>>w>>m; vector<string> s(h); rep(i,h)cin>>s[i]; int sx,sy,gx,gy; rep(i,h){ rep(j,w){ if(s[i][j]=='S'){ sx = i,sy = j; } if(s[i][j]=='G'){ gx = i,gy = j; } } } vector d(h,vector(w,vector<int>(m+1,Inf32))); queue<vector<int>> Q; Q.push({sx,sy,m}); d[sx][sy][m] = 0; while(Q.size()>0){ int x = Q.front()[0]; int y = Q.front()[1]; int k = Q.front()[2]; Q.pop(); vector<int> dx = {1,-1,0,0},dy= {0,0,1,-1}; rep(i,4){ int nx = x + dx[i],ny = y + dy[i]; int nk = k; if(nx<0 || nx>=h || ny<0 || ny>=w) continue; if(s[nx][ny]=='#') continue; if(isdigit(s[nx][ny])){ nk = (s[nx][ny]-'1'); } else if(islower(s[nx][ny])){ if(s[nx][ny]-'a'!=k)continue; } if(d[nx][ny][nk] <= d[x][y][k]+1) continue; d[nx][ny][nk] = d[x][y][k] + 1; Q.push({nx,ny,nk}); } } int ans = Inf32; rep(i,m+1){ ans = min(ans, d[gx][gy][i]); } if(ans == Inf32) ans = -1; cout<<ans<<endl; return 0; }