迷宫寻宝

描述
一个叫ACM的寻宝者找到了一个藏宝图，它根据藏宝图找到了一个迷宫，这是一个很特别的迷宫，迷宫里有N个编过号的门（N<=5)，它们分别被编号为A,B,C,D,E.为了找到宝藏，ACM必须打开门（可以不打开全部的门），但是，开门之前必须在迷宫里找到这个打开这个门所需的所有钥匙（每个门都至少有一把钥匙），例如：现在A门有三把钥匙，ACM就必须找全三把钥匙才能打开A门。现在请你编写一个程序来告诉ACM，他能不能顺利的得到宝藏。

输入
输入可能会有多组测试数据（不超过10组）。
每组测试数据的第一行包含了两个整数M,N(1<N,M<20)，分别代表了迷宫的行和列。接下来的M每行有N个字符，描述了迷宫的布局。其中每个字符的含义如下：
.表示可以走的路
S:表示ACM的出发点
G表示宝藏的位置
X表示这里有墙，ACM无法进入或者穿过。
A,B,C,D,E表示这里是门，a,b,c,d,e表示对应大写字母的门上的钥匙。
注意ACM只能在迷宫里向上下左右四个方向移动。

最后，输入0 0表示输入结束。

输出
每行输出一个YES表示ACM能找到宝藏，输出NO表示ACM找不到宝藏。

样例输入
4 4
S.X.
a.X.
..XG
....
3 4
S.Xa
.aXB
b.AG
0 0


样例输出
YES

NO

思路：

简单的广搜，但是搜索钥匙需要一定的技巧。

1.首先记录打开某个门需要的总钥匙数目。total[]。

2.搜索过程中记录找到的钥匙数。getnum[]。

3.遇到门

1).getnum == total,开门

2).getnum != total && 队列非空，则将起点入队。队列非空则可以搜索其他路径，可能找到剩下的钥匙，再搜索到此门，可能打开。

3).打不开

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
using namespace std;
char map[25][25];
bool visit[25][25];
int getnum[5], total[5]; //getnum搜索到的钥匙数，total门对应总钥匙数
int row, col, starti, startj;
const int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

typedef struct node
{
	int x, y;
};

bool is_error(int x, int y) //越界或者为墙或者搜索过
{
	if(x < 0 || x >= row || y < 0 || y >= col || visit[x][y] || map[x][y] == 'X')
		return 1;
	return 0;
}

bool BFS(int a, int b)
{
	int x, y;
	node in, out;
	queue<node> que;
	in.x = a;
	in.y = b;
	que.push(in);
	while(!que.empty())
	{
		out = que.front();
		que.pop();
		for(int i = 0; i < 4; ++i)
		{
			x = out.x + dir[i][0];
			y = out.y + dir[i][1];
			if(is_error(x, y))
				continue;
			if(map[x][y] >= 'a' && map[x][y] <= 'e')
			{
				getnum[map[x][y] - 'a']++; //搜索到的钥匙数目
				visit[x][y] = 1;
				in.x = x;
				in.y = y;
				que.push(in);
			}
			else if(map[x][y] >= 'A' && map[x][y] <= 'E')
			{
				if(total[map[x][y] - 'A'] == getnum[map[x][y] - 'A']) //搜索到的钥匙和门打开需要的总钥匙数
				{
					visit[x][y] = 1;
					in.x = x;
					in.y = y;
					que.push(in);
				}
				//难点：如果数目不对，且队中还有元素，则起点再入队，等待下次搜索，可能在其他路径找到剩下的钥匙，再搜此点可能打开门
				else if(!que.empty()) //如果队空，则不会再搜索其他路径，不可能找到剩下的钥匙
				{
					in.x = out.x;
					in.y = out.y;
					que.push(in);
				}
				else 
					return false;
			}
			else if(map[x][y] == 'G')
				return true;
			else
			{
				visit[x][y] = 1;
				in.x = x;
				in.y = y;
				que.push(in);
			}
		}
	}
	return false;
}

int main()
{
	//freopen("Input.txt", "r", stdin);
	while(scanf("%d%d", &row, &col) && row && col)
	{
		bool ans;
		memset(map, '0', sizeof(map));
		memset(visit, 0, sizeof(visit));
		memset(getnum, 0, sizeof(getnum));
		memset(total, 0, sizeof(total));
		for(int i = 0; i < row; ++i)
		{
			scanf("%s", map[i]);
			for(int j = 0; j < col; ++j)
			{
				if(map[i][j] == 'S')
				{
					starti = i;
					startj = j;
				}
				else if(map[i][j] >= 'a' && map[i][j] <= 'e')
					total[map[i][j] - 'a']++; //门对应的总钥匙数
			}
		}
		visit[starti][startj] = 1;
		ans = BFS(starti, startj);
		if(ans)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}