bfs poj 2157 maze

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


#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
/*
这里只要判断yes or no,故BFS所有能到达的位置,只要注意当出队的是门时,若不能打开,
则不做操作让门重新入队,避免死循环,这里用limit进行限制
*/
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;
}
相关文章
相关标签/搜索