Maze
Description
Acm, a treasure-explorer, is exploring again. This time he is in a special maze, in which there are some doors (at most 5 doors, represented by ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ respectively). In order to find the treasure, Acm may need to open doors. However, to open a door he needs to find all the door’s keys (at least one) in the maze first. For example, if there are 3 keys of Door A, to open the door he should find all the 3 keys first (that’s three ‘a’s which denote the keys of ‘A’ in the maze). Now make a program to tell Acm whether he can find the treasure or not. Notice that Acm can only go up, down, left and right in the maze.
Input
The input consists of multiple test cases. The first line of each test case contains two integers M and N (1 < N, M < 20), which denote the size of the maze. The next M lines give the maze layout, with each line containing N characters. A character is one of the following: ‘X’ (a block of wall, which the explorer cannot enter), ‘.’ (an empty block), ‘S’ (the start point of Acm), ‘G’ (the position of treasure), ‘A’, ‘B’, ‘C’, ‘D’, ‘E’ (the doors), ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ (the keys of the doors). The input is terminated with two 0’s. This test case should not be processed.
Output
For each test case, in one line output “YES” if Acm can find the treasure, or “NO” otherwise.
Sample Input
4 4 S.X. a.X. ..XG .... 3 4 S.Xa .aXB b.AG 0 0
Sample Output
YES NO
我的代码
这个题目中由于有门的出现，导致在宽搜的时候其实并不能一次性走完所有能走的结点，因此需要根据情况进行多次搜索。根据演绎的思想，我们应该是先进行一次搜索，走遍所有能走到的地方，并且统计寻找到多少钥匙，进一步求出是否能打开一扇新的门。如果能打开一扇门，就以这扇门作为起点继续宽搜，这个过程循环进行到结束的状态。
可以发现，一共只有五扇门，在第一次宽搜之后，就算接下来每一次搜索只能新打开一扇门，那么最多也只要循环五次而已。
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
struct node{
int x,y;
node(){
}
node(int x,int y):x(x),y(y){
}
};
const int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
int m,n,dx,dy,done;
int keyNum[6];//记录钥匙数量
int map[21][21];
int flag[6];//记录门的情况：0为没有这个门，1为出现未访问，-1为可以抵达且访问，2为可以抵达未访问
node door[6];//记录大门位置
node s,g,temp;
queue<node> q;
int check(int x,int y){
if (x>=0&&x<m&&y>=0&&y<n){
return 1;
}else{
return 0;
}
}
void bfs(){
while(!q.empty()&&done==0){
temp=q.front();
q.pop();
for (int i=0;i<4;i++){
dx=temp.x+dir[i][0];
dy=temp.y+dir[i][1];
if (check(dx,dy)==1){
if (map[dx][dy]=='.'){
q.push(node(dx,dy));
map[dx][dy]='X';
}else if (map[dx][dy]>='a'&&map[dx][dy]<='e'){
q.push(node(dx,dy));
keyNum[map[dx][dy]-'a']--;
map[dx][dy]='X';
}else if (map[dx][dy]>='A'&&map[dx][dy]<='E'){
flag[map[dx][dy]-'A']=2;
}else if (map[dx][dy]=='G'){
done=1;
break;
}
}
}
}
}
int main()
{
while (scanf("%d%d",&m,&n)==2&&m!=0){
memset(keyNum,0,sizeof(keyNum));
memset(flag,0,sizeof(flag));
while(!q.empty()){
q.pop();
}
done=0;
for (int i=0;i<m;i++){
for (int j=0;j<n;j++){
scanf(" %c",&map[i][j]);
if (map[i][j]>='a'&&map[i][j]<='e'){
keyNum[map[i][j]-'a']++;
}else if(map[i][j]>='A'&&map[i][j]<='E'){
door[map[i][j]-'A']=node(i,j);
flag[map[i][j]-'A']=1;
}else if(map[i][j]=='S'){
s=node(i,j);
}else if(map[i][j]=='G'){
g=node(i,j);
}
}
}
q.push(s);
map[s.x][s.y]='X';
bfs();
for (int i=0;i<5;i++){
if (done==1){
break;
}else{
for (int j=0;j<5;j++){
if (flag[j]==2&&keyNum[j]<=0){
flag[j]==-1;
while(!q.empty()){
q.pop();
}
q.push(node(door[j].x,door[j].y));
map[door[j].x][door[j].y]='X';
bfs();
}
}
}
}
if (done==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}其实大多数情况下用不到进行5次宽搜，我没有去优化。