2157 Maze

問題概要

縦M横Nのグリッドで表わされる迷路がある。
各グリッドにおいて.は何もないマスを表わし、Xは壁を表わし、a〜eは扉A〜Eの鍵をあらわす。
スタートとゴールはそれぞれS,Gの文字であらわされる。

迷路において、扉を開けるためには、対応する小文字の鍵を全て持っていなければならない。スタートからゴールへの経路があるかを判定せよ。

解法

歩数などは求めなくてよいので、以下のような幅優先探索で解ける。

• 鍵を全て持っている扉のマスに辿り着いたら、それはキューに入れる。
• 鍵を全て拾い終えたら、対応する扉のうち、周囲4マスにすでに行ったマスがあるものをキューに入れる。

2番目の操作がないと、

S..a
AXXX
G...

たぶんこのような迷路でNOを出力してしまう。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int sy,sx,h,w,ky[5];
bool v[20][20]; int tk[5];
char in[20][20];

int main(){
	while(scanf("%d%d ",&h,&w),h){
		rep(i,5)ky[i]=tk[i]=0;
		rep(i,h){
			gets(in[i]);
			rep(j,w){
				char c=in[i][j];
				if('a'<=c&&c<='e')ky[c-'a']++;
				if(c=='S')sy=i,sx=j;
				v[i][j]=0;
			}
		}
		queue<pair<int,int> > Q; Q.push(mp(sy,sx));
		while(!Q.empty()){
			int y=Q.front().first,x=Q.front().second; Q.pop();
			if(v[y][x])continue; v[y][x]=1;
			
			if(in[y][x]=='G'){
				puts("YES"); goto END;
			}
			
			if('a'<=in[y][x]&&in[y][x]<='e'){
				char c=in[y][x];
				if(++tk[c-'a']==ky[c-'a']){
					rep(i,h)rep(j,w)if(in[i][j]==c-'a'+'A'){
						rep(d,4){
							int ny=i+dy[d],nx=j+dx[d];
							if(ny<0||nx<0||ny>=h||nx>=w)continue;
							if(v[ny][nx])Q.push(mp(i,j));
						}
					}
				}
			}
			rep(d,4){
				int ny=y+dy[d],nx=x+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w||v[ny][nx]||in[ny][nx]=='X')continue;
				if('A'<=in[ny][nx]&&in[ny][nx]<='E'&&tk[in[ny][nx]-'A']<ky[in[ny][nx]-'A'])continue;
				Q.push(mp(ny,nx));
			}
		}
		puts("NO"); END:;
	}
	return 0;
}