题目大意:S是起点,G是 终点,"."是可走的路,“X”是不可走的路
解决:BFS 本题有些难度,因为若为钥匙,将钥匙吃了之后,将这个点变为“.”,若为门,判断是否对应该门的钥匙都拿到手了,若都拿到手了,可以将这个门打开,即变为“.”,否则,等这个点周围的所有点都进队列后,若队列为空说明路都走过了,一定无法通过,若队列非空,说明还有其他的路可以走,将这个点入队列,一会等着把钥匙都得到了,在出队列判断。
#include <iostream> #include <cstdio> #include <queue> using namespace std; char map[22][22]; int m,n; int sx,sy; bool found; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; int key[5]; struct node { int x,y; node(int xx,int yy){x=xx;y=yy;} node(){}; }; bool bfs() { queue<node> q; q.push(node(sx,sy)); map[sx][sy]='X'; node now,next; char c; bool flag=false; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0;i<4;i++) { next=node(now.x+dx[i],now.y+dy[i]); if(next.x>=0 && next.x<m && next.y>=0 && next.y<n) { c=map[next.x][next.y]; if(c=='G')return true; if(c>='a' && c<='e') {//是钥匙的话,钥匙个数减1 key[c-'a']--; map[next.x][next.y]='X'; q.push(next); } else if(c>='A' && c<='E') {//若为锁,判断钥匙数是否为0,为0的话,打开门,否则,标记下,等着其他的点进队 if(!key[c-'A']){map[next.x][next.y]='X';q.push(next);} else flag=true; } else if(c=='.') { map[next.x][next.y]='X'; q.push(next); } } } if(flag) {//若其他的点进队后,仍然为空,没路了,否则,入队列,等待下次判断 if(q.empty())return false; else {flag=false; q.push(now);} } } return false; } int main() { while(scanf("%d%d",&m,&n),n||m) { key[0]=key[1]=key[2]=key[3]=key[4]=0; getchar(); for(int i=0;i<m;i++)scanf("%s",map[i]); for(int i=0;i<m;i++) for(int j=0;j<n;j++) { if(map[i][j]=='S'){sx=i;sy=j;} else if(map[i][j]>='a' && map[i][j]<='e')key[map[i][j]-'a']++; } if(bfs() )puts("YES"); else puts("NO"); } system("pause"); return 0; }