結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:32:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 112 ms / 3,000 ms |
コード長 | 2,855 bytes |
コンパイル時間 | 2,251 ms |
コンパイル使用メモリ | 204,924 KB |
実行使用メモリ | 13,820 KB |
最終ジャッジ日時 | 2025-07-11 21:32:14 |
合計ジャッジ時間 | 5,029 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:57:11: warning: ‘sh’ may be used uninitialized [-Wmaybe-uninitialized] 57 | Q.push({sh,sw,0}); | ~~~~~~^~~~~~~~~~~ main.cpp:42:9: note: ‘sh’ was declared here 42 | int sh,sw,gh,gw; | ^~ main.cpp:57:11: warning: ‘sw’ may be used uninitialized [-Wmaybe-uninitialized] 57 | Q.push({sh,sw,0}); | ~~~~~~^~~~~~~~~~~ main.cpp:42:12: note: ‘sw’ was declared here 42 | int sh,sw,gh,gw; | ^~ main.cpp:42:15: warning: ‘gh’ may be used uninitialized [-Wmaybe-uninitialized] 42 | int sh,sw,gh,gw; | ^~ main.cpp:42:18: warning: ‘gw’ may be used uninitialized [-Wmaybe-uninitialized] 42 | int sh,sw,gh,gw; | ^~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; } #define vi vector<int> #define vl vector<ll> #define vii vector<pair<int,int>> #define vll vector<pair<ll,ll>> #define vvi vector<vector<int>> #define vvl vector<vector<ll>> #define vvii vector<vector<pair<int,int>>> #define vvll vector<vector<pair<ll,ll>>> #define vst vector<string> #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=505,INF=15<<26; int dis[MAX][MAX][10]; vi dh={0,1,0,-1},dw={1,0,-1,0}; int main(){ std::ifstream in("text.txt"); std::cin.rdbuf(in.rdbuf()); cin.tie(0); ios::sync_with_stdio(false); int H,W,N;cin>>H>>W>>N; vst S(H); for(int i=0;i<H;i++){ cin>>S[i]; } int sh,sw,gh,gw; for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ if(S[i][j]=='S'){ sh=i; sw=j; } if(S[i][j]=='G'){ gh=i; gw=j; } } } queue<array<int,3>> Q; Q.push({sh,sw,0}); for(int i=0;i<H;i++){ for(int j=0;j<W;j++){ for(int k=0;k<10;k++){ dis[i][j][k]=INF; } } } dis[sh][sw][0]=0; while(!Q.empty()){ auto [h,w,x]=Q.front();Q.pop(); int d=dis[h][w][x]; //cout<<h<<" "<<w<<" "<<x<<" "<<d<<endl; for(int k=0;k<4;k++){ int toh=h+dh[k],tow=w+dw[k]; if(toh<0||toh>=H||tow<0||tow>=W) continue; if(S[toh][tow]=='#') continue; int tox=x; if(S[toh][tow]=='.'){ if(chmin(dis[toh][tow][tox],d+1)) Q.push({toh,tow,tox}); } if(S[toh][tow]=='S'){ if(chmin(dis[toh][tow][tox],d+1)) Q.push({toh,tow,tox}); } if(S[toh][tow]=='G'){ if(chmin(dis[toh][tow][tox],d+1)) Q.push({toh,tow,tox}); } if('1'<=S[toh][tow]&&S[toh][tow]<='9'){ tox=(S[toh][tow]-'0'); if(chmin(dis[toh][tow][tox],d+1)) Q.push({toh,tow,tox}); } if('a'<=S[toh][tow]&&S[toh][tow]<='i'&&(S[toh][tow]-'a')==x-1){ if(chmin(dis[toh][tow][tox],d+1)) Q.push({toh,tow,tox}); } } } int ans=INF; for(int k=0;k<10;k++) chmin(ans,dis[gh][gw][k]); if(ans==INF) ans=-1; cout<<ans<<endl; }