結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 22:22:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 155 ms / 3,000 ms |
コード長 | 2,290 bytes |
コンパイル時間 | 2,269 ms |
コンパイル使用メモリ | 212,572 KB |
実行使用メモリ | 21,888 KB |
最終ジャッジ日時 | 2025-07-11 22:22:10 |
合計ジャッジ時間 | 5,530 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long // #define rep(i,n) for(int i=0;i<(int)n;i++) #define rep(i,r) for(ll i=0;i<(ll)r;i++) #define vi vector<int> #define vl vector<ll> #define vd vector<double> #define vb vector<bool> #define vs vector<string> #define vc vector<char> #define ull unsigned long long #define chmax(a,b) a=max(a,b) #define chmin(a,b) a=min(a,b) // ll inf=(1ll<<62); // ll rui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a*rui(a*a,b/2); // return rui(a*a,b/2); // } // ll const mod=998244353ll; // ll modrui(ll a,ll b){ // if(b==0)return 1; // if(b%2==1) return a%mod*modrui(a%mod*a%mod,b/2)%mod; // return modrui(a%mod*a%mod,b/2)%mod; // } // ll inv(ll x){ // return modrui(x,mod-2); // } void solve(){ ll h,w,m;cin >> h >> w >> m; vs room(h); rep(i,h)cin >> room[i]; ll const dx[4]={0,1,0,-1},dy[4]={1,0,-1,0}; vector<vector<vb>> used(h,vector<vb>(w,vb(10,0))); deque<array<ll,4>> dq(0); rep(i,h)rep(j,w)if(room[i][j]=='S'){ dq.push_back({i,j,0,0}); used[i][j][0]=1; } while(!dq.empty()){ ll i=dq[0][0],j=dq[0][1],key=dq[0][2],d=dq[0][3]; dq.pop_front(); rep(k,4){ ll ni=i+dx[k],nj=j+dy[k]; if(0<=ni && ni<h && 0<=nj && nj<w && !used[ni][nj][key] && room[ni][nj]!='#'){ if(room[ni][nj]=='.' || room[ni][nj]=='S'){ dq.push_back({ni,nj,key,d+1}); used[ni][nj][key]=1; } else if(islower(room[ni][nj])){ if(key!=0 && key==(ll)(room[ni][nj]-'a'+1)){ dq.push_back({ni,nj,key,d+1}); used[ni][nj][key]=1; } } else if(room[ni][nj]=='G'){ cout << d+1 << endl; return; } else if(!used[ni][nj][room[ni][nj]-'0']){//数字 dq.push_back({ni,nj,room[ni][nj]-'0',d+1}); used[ni][nj][key]=1; used[ni][nj][room[ni][nj]-'0']=1; } } } } cout << -1 << endl; } int main(){ ll t=1; // cin >> t; while(t--)solve(); }