走迷宫拿宝藏，拿到所有对应的钥匙才能开门
*解法：从起点bfs，遇到门时先放入队列中，取出的时候看钥匙够不够决定开不开门，如果不够就把它再放回队列继续往下走，当队列里只有几个门循环的时候就可以退出，所以记一个T<400
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;
#define INF 1e9+10
char a[22][22];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int vis[22][22], use[22][22];
int n, m, key[6], num[6], flag;
queue<int> q;
void bfs(int sx, int sy)
{
while(!q.empty()) q.pop();
vis[sx][sy] = 1;
q.push(sx * m + sy);
int T = 0;
//队列里是能达到的点，标记vis的是能到达并拓展的点
while(!q.empty() && T < 400)
{
T++;
int x = q.front() / m, y = q.front() % m; q.pop();
if(a[x][y] >= 'A' && a[x][y] <= 'E')
{
if(key[a[x][y] - 'A'] == num[a[x][y] - 'A'])//开门
{
memset(vis, 0, sizeof(vis));
a[x][y] = '.';
vis[x][y] = 1;
}
else//不开门
{
q.push(x * m + y);
continue;
}
}
for(int i = 0; i < 4; i++)
{
int xx = x + dx[i], yy = y + dy[i];
if(xx >= 0 && xx < n && yy >= 0 && yy < m && !vis[xx][yy] && a[xx][yy] != 'X')
{
if(a[xx][yy] == 'G') {flag = 1; return;}
if(a[xx][yy] == '.')
{
vis[xx][yy] = 1;
q.push(xx * m + yy);
}
if(a[xx][yy] >= 'a' && a[xx][yy] <= 'e')
{
key[a[xx][yy] - 'a']++;
vis[xx][yy] = 1;
a[xx][yy] = '.';
q.push(xx * m + yy);
}
if(a[xx][yy] >= 'A' && a[xx][yy] <= 'E')
{
q.push(xx * m + yy);//放入队列但不标记
}
}
}
}
}
int main()
{
while(1)
{
scanf("%d %d", &n, &m);
if(n == 0 && m == 0) break;
int sx, sy;
memset(key, 0, sizeof(key));
memset(num, 0, sizeof(num));
memset(vis, 0, sizeof(vis));
memset(use, 0, sizeof(use));
for(int i = 0; i < n; i++)
{
scanf(" %s", a[i]);
for(int j = 0; j < m; j++)
{
if(a[i][j] == 'S') sx = i, sy = j;
if(a[i][j] >= 'a' && a[i][j] <= 'e') num[a[i][j] - 'a']++;
}
}
for(int i = 0; i < 5; i++) if(num[i] == 0) num[i] = INF;
flag = 0;
bfs(sx, sy);
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}