这道题，用floodfill做的，首先floodfill把所有能走到的点走完，然后统计找到的钥匙数量，如果某个门的钥匙全部找到，就把相应的门打开，重新floodfill，直到达到G点或者不能再扩展。
注意本题每行后有若干空格，我就是没有注意这点，被玩了几个小时……
#include<iostream>
using namespace std;
char map[21][21];
int h,w;
bool visit[21][21];
int num[6],cnt[6],open[6],sx,sy,ex,ey;
bool flag=0;
bool ok(int x,int y)//是否可达
{
if(x>=1&&x<=h&&y>=1&&y<=w&&!visit[x][y]&&map[x][y]!='X'&&(map[x][y]<'A'||map[x][y]>'E'))
return 1;
return 0;
}
int searchdoor(int q)//打开门
{
int i,j;
for(i=1;i<=h;i++)
{
for(j=1;j<=w;j++)
{
if(map[i][j]=='A'+q-1)
map[i][j]='.';
}
}
open[q]=1;
return 0;
}
bool iskey(int x,int y)//判断是否为钥匙
{
if(map[x][y]>='a'&&map[x][y]<='e')
return 1;
return 0;
}
int floodfill(int x,int y)//灌水
{
bool canmove=0;
if(x==ex&&y==ey)
{
flag=1;
return 0;
}
visit[x][y]=1;
if(iskey(x,y))
{
cnt[map[x][y]-'a'+1]++;
}
if(ok(x+1,y))
{
canmove=1;
floodfill(x+1,y);
}
if(ok(x-1,y))
{
canmove=1;
floodfill(x-1,y);
}
if(ok(x,y+1))
{
canmove=1;
floodfill(x,y+1);
}
if(ok(x,y-1))
{
canmove=1;
floodfill(x,y-1);
}
if(!canmove)
{
int i;
for(i=1;i<=5;i++)
{
if(cnt[i]>0&&cnt[i]==num[i]&&!open[i])
{
searchdoor(i);
memset(visit,0,sizeof(visit));
memset(cnt,0,sizeof(cnt));
floodfill(sx,sy);
}
}
}
}
int main()
{
while(cin>>h>>w)
{
if(h==0&&w==0)
break;
memset(visit,0,sizeof(visit));
memset(map,'\0',sizeof(map));
memset(num,0,sizeof(num));
memset(cnt,0,sizeof(num));
memset(open,0,sizeof(open));
int i,j;
for(i=1;i<=h;i++)
{
for(j=1;j<=w;j++)
{
cin>>map[i][j];
if(map[i][j]=='S')
{
sx=i;
sy=j;
}
if(map[i][j]=='G')
{
ex=i;
ey=j;
}
if(map[i][j]>='a'&&map[i][j]<='e')
{
num[map[i][j]-'a'+1]++;
}
}
}
flag=0;
floodfill(sx,sy);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
system("pause");
return 0;
}