PKU 2157 Maze
http://poj.org/problem?id=2157
迷路探索。
迷路には'A'から'E'で表されるドアがあり、それに対応する小文字のマスを全て通らないとそのマスを通過できないというふうになっている。
このとき、スタートからゴールまで辿りつけるかどうかを判定するという問題。
幅優先探索。
鍵を一個取るたびに訪れたフラグを初期化して探索しました。
いろいろと迷走して何回かWA
bool vis[20][20]; string in[20]; main(){ int n,m; while(cin>>n>>m,n|m){ memset(vis,0,sizeof(vis)); int sx,sy; map<char,int> app; rep(i,n){ cin>>in[i]; rep(j,SZ(in[i])){ if(in[i][j]=='S')sx=i,sy=j,in[i][j]='.'; else if(islower(in[i][j]))app[in[i][j]]++; } } queue<PI> q; q.push(mp(sx,sy)); bool ok=false; int turn=0; while(!q.empty()){ int cx=q.front().F,cy=q.front().S;q.pop(); if(in[cx][cy]=='G'){ ok=true; break; } if(vis[cx][cy])continue; if(islower(in[cx][cy])){ app[in[cx][cy]]--; in[cx][cy]='.'; memset(vis,0,sizeof(vis)); } vis[cx][cy]=true; rep(i,4){ int nx=cx+dx[i],ny=cy+dy[i]; if(nx<0 || n<=nx || ny<0 || m<=ny || in[nx][ny]=='X' || vis[nx][ny])continue; if('a'<=in[nx][ny] && in[nx][ny]<='e'){ q.push(mp(nx,ny)); }else if('A'<=in[nx][ny] && in[nx][ny]<='E'){ if(app.count(tolower(in[nx][ny])) && app[tolower(in[nx][ny])]==0) q.push(mp(nx,ny)); }else q.push(mp(nx,ny)); } } cout<<(ok?"YES":"NO")<<endl; } }