# bfs poj 2157 maze

http://poj.org/problem?id=2157

```#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
/*

*/
using namespace std;
struct node
{
int x,y;
node(int a=0,int b=0){x=a;y=b;}
};
int limit,m,n,key[5],vis[20][20];
int move[4][2]={0,1,1,0,0,-1,-1,0};
char maze[20][20];

bool bfs(int x,int y)
{
queue<node> que;
node p;
limit=0;
que.push(node(x,y));
while(!que.empty()&&limit<400)
{
limit++;
p=que.front();
que.pop();
if(maze[p.x][p.y]>='A'&&maze[p.x][p.y]<='E')
{
if(key[maze[p.x][p.y]-'A']==0)
vis[p.x][p.y]=1;
else
{
que.push(p);
continue;
}
}
for(int i=0;i<4;++i)
{
x=p.x+move[i][0];
y=p.y+move[i][1];
if(x>=0&&x<m&&y>=0&&y<n&&!vis[x][y])
{
if(maze[x][y]=='G')
return 1;
if(maze[x][y]>='A'&&maze[x][y]<='E')
que.push(node(x,y));
if(maze[x][y]>='a'&&maze[x][y]<='e')
{
key[maze[x][y]-'a']--;
vis[x][y]=1;
que.push(node(x,y));
}
if(maze[x][y]=='.')
{
vis[x][y]=1;
que.push(node(x,y));
}
}
}
}
return 0;
}
int main()
{
while(scanf("%d%d",&m,&n)==2&&(m||n))
{
memset(vis,0,sizeof(vis));
memset(key,0,sizeof(key));
int i,j,x,y;
for(i=0;i<m;++i)
{
scanf("%s",maze[i]);
for(j=0;j<n;++j)
if(maze[i][j]=='S')
{
x=i;
y=j;
vis[x][y]=1;
}
else if(maze[i][j]>='a'&&maze[i][j]<='e')
key[maze[i][j]-'a']++;
}

printf(bfs(x,y)?"YES\n":"NO\n");
}
return 0;
}
```