hdoj 1429 胜利大逃亡(续) 【BFS+状态压缩】

题目：

同样题目：

题意：中文的，自己看

分析：题目是求最少的逃亡时间。确定用BFS

这个题目的难点在于有几个锁对于几把钥匙。唯一的相应关系，不能用直接的标记法，由于一个图可能须要搜索多次。

细致分析的话会发现。图的搜索次数是和钥匙的出现次数相关，那么我们能够用二进制的0 和 1 来表示第几把钥匙出现过没有。所以我们能够用状态压缩来标记那个钥匙出现过，然后用三维标记，第三维表示出现几个钥匙了的情况下图的点的搜索情况。其它就和简单的一样。

AC代码：

#include <cstdio>

#include<iostream>

#include <queue>

#include <cstring>

using namespace std;

const int N = 25;

char map[N][N];

int vis[N][N][1<<11];

struct Node

{

    int x,y,step;

    int key;

};

int dx[6]={0,0,1,-1};

int dy[6]={1,-1,0,0};

int m,n,t;

int BFS(Node st,Node en)

{

    memset(vis,0,sizeof(vis));

    st.step = 0;st.key=0;

    queue<Node> q;

    q.push(st);

    Node tmp1,tmp2;

    while(!q.empty())

    {

        tmp1 = q.front();

        q.pop();

        if(tmp1.x==en.x && tmp1.y==en.y)

            return tmp1.step;

        for(int i=0;i<4;i++)

        {

            tmp2.x=tmp1.x+dx[i];

            tmp2.y=tmp1.y+dy[i];

            tmp2.step = tmp1.step+1;

            tmp2.key = tmp1.key;

            if(map[tmp2.x][tmp2.y]>='a' && map[tmp2.x][tmp2.y]<='j')

                tmp2.key = tmp2.key|(1<<(map[tmp2.x][tmp2.y]-'a'));

            if(map[tmp2.x][tmp2.y]=='*' || tmp2.step>=t)

                continue;

            if(vis[tmp2.x][tmp2.y][tmp2.key]==0 && tmp2.x>=1 && tmp2.y>=1 && tmp2.x<=m && tmp2.y<=n)

            {

                vis[tmp2.x][tmp2.y][tmp2.key]=1;

                if(map[tmp2.x][tmp2.y]>='A' && map[tmp2.x][tmp2.y]<='J')

                {

                    if(tmp2.key&(1<<map[tmp2.x][tmp2.y]-'A'))

                        q.push(tmp2);

                }

                else

                    q.push(tmp2);

            }

        }

    }

    return -1;

}

int main()

{

    //freopen("Input.txt","r",stdin);

    while(~scanf("%d%d%d",&m,&n,&t))

    {

        Node st,en;

        for(int i=1;i<=m;i++)

        {

            getchar();

            for(int j=1;j<=n;j++){

                scanf("%c",&map[i][j]);

                if(map[i][j]=='@')

                    st.x=i,st.y=j;

                if(map[i][j]=='^')

                    en.x=i,en.y=j;

            }

        }

        int ans=BFS(st,en);

        if(ans<t)

            printf("%d\n",ans);

        else

            puts("-1");

    }

    return 0;

}