結果

問題 No.3199 Key-Door Grid
コンテスト
ユーザー askr58
提出日時 2025-07-11 21:36:41
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 150 ms / 3,000 ms
コード長 1,119 bytes
コンパイル時間 3,488 ms
コンパイル使用メモリ 286,328 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2025-07-11 21:36:49
合計ジャッジ時間 6,962 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
	int h,w,m;
	cin>>h>>w>>m;
	vector<string> s(h);
	for(int i=0;i<h;i++)cin>>s[i];
	vector<vector<vector<int>>> dist(h,vector<vector<int>>(w,vector<int>(10,1e9)));
	queue<pair<int,int>> bfs;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
		if(s[i][j]=='S'){	
			bfs.push(make_pair(i*w+j,0));
			dist[i][j][0]=0;
		}
	}
	int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
	while(!bfs.empty()){
		int x=bfs.front().first/w,y=bfs.front().first%w,key=bfs.front().second;
		bfs.pop();
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx<0||nx>=h||ny<0||ny>=w||s[nx][ny]=='#')continue;
			int nkey=key;
			if('1'<=s[nx][ny]&&s[nx][ny]<='9')nkey=s[nx][ny]-'0';
			if(dist[nx][ny][nkey]!=1e9)continue;
			if('a'<=s[nx][ny]&&s[nx][ny]<='i'&&'a'+(nkey-1)!=s[nx][ny])continue;
			bfs.push(make_pair(nx*w+ny,nkey));
			dist[nx][ny][nkey]=dist[x][y][key]+1;
		}
	}
	int ans=-1;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
		if(s[i][j]=='G'){
			int res=1e9;
			for(int k=0;k<10;k++)res=min(res,dist[i][j][k]);
			if(res!=1e9)ans=res;
		}
	}
	cout<<ans<<endl;
}
0