题目连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=82
此题在基础BFS上加入了门和钥匙，要找齐所有钥匙才能开门，所以要对门特殊处理。
1.先统计下各类钥匙的数量，再记下门的位置。
2.进行BFS,遇到钥匙时，入队，计数各类已找到的钥匙，然后判断是否钥匙找齐，如果找齐，找到对应的门，如果门之前是否访问过，则门入队。（可能此门被障碍堵住，无法进去，所以不能直接加入，只能以前访问过的加入）。
3.如果遇到门，判断钥匙是否找齐，若齐，入队，标记已访问；不齐，不入队，标记已访问。
4.其他的按正常的BFS即可。
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct point
{
int x,y;
}s,e,men[6];
int n,m;
int h[4][2]={-1,0,1,0,0,1,0,-1};
int yaosum[6],findyao[6],bz[30][30];
char map[30][30];
queue<point> q;
int bfs(point s)
{
int i; point temp,t;
while(!q.empty()) q.pop();
q.push(s); bz[s.x][s.y]=1;
while(!q.empty())
{
temp=q.front(); q.pop();
if(temp.x==e.x&&temp.y==e.y) return 1;
for(i=0;i<4;i++)
{
t.x=temp.x+h[i][0]; t.y=temp.y+h[i][1];
if(t.x>=0&&t.x<n&&t.y>=0&&t.y<m&&map[t.x][t.y]!='X')
{
if(map[t.x][t.y]>='A'&&map[t.x][t.y]<='E'&&!bz[t.x][t.y])//是门，看是否能打开
{
if(findyao[map[t.x][t.y]-'A']==yaosum[map[t.x][t.y]-'A'])//钥匙齐，可以打开
{
q.push(t); bz[t.x][t.y]=1;
}
else bz[t.x][t.y]=1; //无法打开，先标记已访问
}
else if(map[t.x][t.y]>='a'&&map[t.x][t.y]<='e'&&!bz[t.x][t.y]) //是钥匙
{
findyao[map[t.x][t.y]-'a']++;
q.push(t); bz[t.x][t.y]=1;
//判断钥匙是不是已经找齐，并且对应的门是否已访问过，若钥匙齐，门之前访问过，可以把门入队
if(findyao[map[t.x][t.y]-'a']==yaosum[map[t.x][t.y]-'a'])
{
point m; m.x=men[map[t.x][t.y]-'a'].x; m.y=men[map[t.x][t.y]-'a'].y;
if(bz[m.x][m.y]) q.push(m); //门入队
}
}
else if((map[t.x][t.y]=='.'||map[t.x][t.y]=='G')&&!bz[t.x][t.y])
{
q.push(t); bz[t.x][t.y]=1;
}
}
}
}
return 0;
}
int main(int argc, char *argv[])
{
int i,j;
while(cin>>n>>m&&(n+m))
{
memset(yaosum,0,sizeof(yaosum));
memset(findyao,0,sizeof(findyao));
memset(bz,0,sizeof(bz));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
cin>>map[i][j];
if(map[i][j]=='S') {s.x=i;s.y=j;}
else if(map[i][j]=='G') {e.x=i; e.y=j;}
else if(map[i][j]>='a'&&map[i][j]<='e') yaosum[map[i][j]-'a']++;
else if(map[i][j]>='A'&&map[i][j]<='E')
{
men[map[i][j]-'A'].x=i; men[map[i][j]-'A'].y=j;
}
}
if(bfs(s)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}