HDOJ-1885Key Task（状态压缩）

约定不等于承诺〃 2022-08-05 08:52 119阅读 0赞

迷宫问题，有钥匙和门的 bfs +  状态压缩

有四个钥匙四把锁，求最短路径

具体解释都在代码里面，可以多看一下，并且和下一边状态压缩问题一起对应这看一下比较好。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    
    using namespace std;
    #define MAXN 110
    
    struct Node
    {
        int x,y,key;
        int step;
    };
    
    char map[MAXN][MAXN];  //地图
    bool mark[MAXN][MAXN][22];//标记是否访问
    int dir[4][2]={
       {-1,0},{1,0},{0,-1},{0,1}}; //方向
    int n,m;
    Node st;
    
    char Door[4]={'B','Y','R','G'};
    char Key[4]={'b','y','r','g'};
    
    void bfs()
    {
        memset(mark,false,sizeof(mark));
        queue<Node>Q;
        Node p,q;
        st.key=st.step=0;
        mark[st.x][st.y][st.key]=true;
        Q.push(st);
        while(!Q.empty()){
            p=Q.front();
            Q.pop();
            if(map[p.x][p.y]=='X'){
                printf("Escape possible in %d steps.\n",p.step);
                return ;
            }
            for(int i=0;i<4;i++)
            {
                q.x=p.x+dir[i][0];
                q.y=p.y+dir[i][1];
                q.step=p.step+1;
                q.key=p.key;
                if(q.x<1||q.x>n||q.y<1||q.y>m||map[q.x][q.y]=='#')
                    continue;
                if(isupper(map[q.x][q.y])&&map[q.x][q.y]!='X')
                {//isupper判断是否是大写字母(锁的位置)
                    for(int j=0;j<4;j++)
                    {
                        if(map[q.x][q.y]==Door[j])   //找是哪个锁
                        {
                            if(q.key&(1<<j))   //q.key,是否有该锁的钥匙
                            {//没有
                                if(!mark[q.x][q.y][q.key])
                                {
                                    mark[q.x][q.y][q.key]=true;
                                    Q.push(q);
                                }
                                break;
                            }
                        }
                    }
                }
                else if(islower(map[q.x][q.y]))
                {//islower()判断是否是小写字母(钥匙的位置)
                    for(int j=0;j<4;j++)
                    {
                        if(map[q.x][q.y]==Key[j])  //找是哪个钥匙
                        {
                            if((q.key&(1<<j))==0)  
                            {
                                q.key+=(1<<j);  //加上这把钥匙（标记这个钥匙的状态）
                            }
                            if(!mark[q.x][q.y][q.key])
                            {
                                mark[q.x][q.y][q.key]=true;
                                Q.push(q);
                            }
                        }
                    }
                }
                else
                {
                    if(!mark[q.x][q.y][q.key])
                    {
                        mark[q.x][q.y][q.key]=true;
                        Q.push(q);
                    }
                }
            }
        }
        puts("The poor student is trapped!");
    }
    
    
    int main(){
        while(scanf("%d%d",&n,&m),(n+m))
        {
            for(int i=1;i<=n;i++)
            {
                scanf("%s",map[i]+1);
                for(int j=1;j<=m;j++)
                {
                    if(map[i][j]=='*')
                    {
                        st.x=i;st.y=j;
                    }
                }
            }
            bfs();
        }
        return 0;
    }