【POJ2157】Maze

题目链接：http://poj.org/problem?id=2157
题解：
BFS爆搜
建一个bool1数组表示一个门是否走过，一个bool2数组表示任意一个点是否走过
每次走到一个钥匙，该钥匙数+1，如果这个钥匙对应的门曾经到过，而且钥匙数够了，把门放进队列里，没有到过就个普通的点一样处理
如果走到一个门，如果钥匙数等于零，那么把这个门加进队列里，如果不为零，标记为到过这个门

感觉思路没问题，POJ的discuss里的数据也都过了，可就是A不了，怒改4h水过…
这种爆搜题真是无话可说…….

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

int n,m;
int vis[101][101],vis_door[101][101];
char map[101][101];

int x [ 5 ] = { 1,-1, 0, 0 } ;
int y [ 5 ] = { 0, 0, 1,-1 } ;

struct node
{
    int x,y;
};
struct key
{
    int tot,cnt;
}k[101];

int main()
{
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        bool flag=0,a;
        memset(k,0,sizeof(k));
        memset(vis,0,sizeof(vis));
        memset(vis_door,0,sizeof(vis_door));
        for(int i=1;i<=n;i++) scanf("%s",map[i]+1);
        queue<node> q;
        node st,t,p;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(map[i][j]=='S') st.x=i,st.y=j;
                else if(map[i][j]=='X') vis[i][j]=1;
                else if(map[i][j]>='a'&&map[i][j]<='e') k[map[i][j]-'a'].tot++;
        q.push(st);
        while(!q.empty())
        {
            p=q.front();
            q.pop();
            for(int i=0;i<=3;i++)
            {
                int nx=p.x+x[i];
                int ny=p.y+y[i];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m)
                    if(!vis[nx][ny])
                    {
                        if(map[nx][ny]>='a'&&map[nx][ny]<='e')
                        {
                            if(++k[map[nx][ny]-'a'].cnt==k[map[nx][ny]-'a'].tot&&k[map[nx][ny]-'a'].cnt>=1)
                            {
                                for(int ii=1;ii<=n;ii++)
                                    for(int jj=1;jj<=m;jj++)
                                    if(map[ii][jj]==map[nx][ny]+'A'-'a')
                                    {
                                        node hh;
                                        hh.x=ii;
                                        hh.y=jj;
                                        if(vis_door[ii][jj])
                                        {
                                            q.push(hh);
                                            vis[ii][jj]=1;  
                                        }
                                    }
                            }
                            t.x=nx;
                            t.y=ny;
                            q.push(t);
                            vis[nx][ny]=1;
                        }
                        else if(map[nx][ny]=='G')
                        {
                            flag=1;
                            break;
                        }
                        else if(map[nx][ny]>='A'&&map[nx][ny]<='E')
                        {
                            if(k[map[nx][ny]-'A'].tot==k[map[nx][ny]-'A'].cnt&&k[map[nx][ny]-'A'].cnt>=1)
                            {
                                t.x=nx;
                                t.y=ny;
                                q.push(t);
                                vis[nx][ny]=1;
                            }
                            else vis_door[nx][ny]=1;
                        }
                        else if(map[nx][ny]=='.')
                        {
                            t.x=nx;
                            t.y=ny;
                            q.push(t);
                            vis[nx][ny]=1;
                        }
                    }
            }
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}