Hdu 1429（状态压缩）

喜欢ヅ旅行 2022-08-05 08:52 179阅读 0赞

有钥匙和门的 bfs +  状态压缩

一个十把钥匙和锁，分别为a,b......j。当所用的步数小于t即可。

和上一篇对应着来看，加强状态压缩的理解。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    
    int n,m,t,ans;
    char map[21][21];
    int dir[4][2]={1,0,-1,0,0,1,0,-1};
    int vis[21][21][1<<10];
    //visit第三维是存放钥匙的，十种不同的钥匙用十个不同的二进制来存放
    //0000000000，所以是1<<10(1024)，相应的位置上是0代表没有该种钥匙
    
    struct node
    {
        int x,y,dis,key;
        //一般这里面除了step之外有几个参数，visit数组就有几维
        node(int _x=0,int _y=0,int _dis=0,int _key=0):x(_x),y(_y),dis(_dis),key(_key){};
    };
    
    node s;
    
    void BFS()
    {
        ans=-1;
        memset(vis,0,sizeof(vis));
        vis[s.x][s.y][s.key]=1;
        queue <node> q;
        q.push(s);
        while(!q.empty())
        {
            node tt=q.front();
            q.pop();
            for(int k=0;k<4;k++)
            {
                int x=tt.x+dir[k][0];
                int y=tt.y+dir[k][1];
                if(x>=0&&x<n&&y>=0&&y<m&&map[x][y]!='*'&&!vis[x][y][tt.key])
                {
                    if(map[x][y]=='.'||map[x][y]=='@')
                    {
                        //起点或者普通的可通过的路
                        vis[x][y][tt.key]=1;
                        q.push(node(x,y,tt.dis+1,tt.key));
                    }
                    if(map[x][y]=='^')
                    {
                        //出口
                        if(tt.dis+1<t)ans=tt.dis+1;
                        return;
                    }
                    if(map[x][y]>='A'&&map[x][y]<='J')
                    {
                        //有锁的地方，查找是否有该锁的钥匙
                        int key=1<<(map[x][y]-'A');
                        //对应钥匙应该在的位
                        if(tt.key&key)
                        {
                            //tt.key的该位是否是一个1（钥匙）
                            vis[x][y][tt.key]=1;
                            q.push(node(x,y,tt.dis+1,tt.key));
                        }
                    }
                    if(map[x][y]>='a'&&map[x][y]<='j')
                    {
                        //有钥匙的地方
                        int key=1<<(map[x][y]-'a');
                        if(!vis[x][y][tt.key|key])
                        {
                            //tt.key|key,将钥匙所在的位加进去
                            vis[x][y][tt.key|key]=1;
                            q.push(node(x,y,tt.dis+1,tt.key|key));
                        }
                    }
                }
            }
        }
    }
    
    int main()
    {
        while(scanf("%d%d%d",&n,&m,&t)==3)
        {
            for(int i=0;i<n;i++)
            {
                scanf("%s",map[i]);
                for(int j=0;j<m;j++)
                {
                    if(map[i][j]=='@')
                    {
                        s.x=i;s.y=j;s.dis=0,s.key=0;
                    }
                }
            }
            BFS();
            printf("%d\n",ans);
        }
    }