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

以你之姓@ 2022-08-11 16:38 142阅读 0赞

题目：[hdoj 1429 胜利大逃亡(续) ][hdoj 1429 _]

相同题目：

题意：中文的，自己看

分析：题目是求最少的逃亡时间，确定用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;
    }

[hdoj 1429 _]: http://acm.hdu.edu.cn/showproblem.php?pid=1429