HDU-1429（胜利大逃亡续）-BFS+状态压缩

痛定思痛。 2022-07-16 02:22 161阅读 0赞

# 胜利大逃亡(续) #

**Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)**

Total Submission(s): 8029    Accepted Submission(s): 2865

Problem Description

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……  
  
这次魔王汲取了上次的教训，把Ignatius关在一个n\*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

Input

每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:  
  
. 代表路  
\* 代表墙  
@ 代表Ignatius的起始位置  
^ 代表地牢的出口  
A-J 代表带锁的门,对应的钥匙分别为a-j  
a-j 代表钥匙，对应的门分别为A-J  
  
每组测试数据之间有一个空行。

Output

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。

Sample Input

4 5 17
    @A.B.
    a*.*.
    *..*^
    c..b*
    
    4 5 16
    @A.B.
    a*.*.
    *..*^
    c..b*

Sample Output

16
    -1

题目大意：给你一张（n\*m）地图，在地图中‘@’为你的起始位置，‘^’为目标即你需要到达的位置，‘\*’为墙，不可走的点，‘.’为空地，你可以走的点，小写字母为钥匙，大写字母为门，要打开门必须要拥有对应小写字母的钥匙才能打开，现在给你一个时间限定，你必须在ts之前（不能等于）并且以最快的时间从起点找到目标位置，开始时间为0，每移动一格为1s，如果能找到，输出最少的时间，否则输出-1

题目思路：开始看到题目时首先想到的是bfs求最短的时间到达，但是关键在于：中间找到钥匙要存起来，遇到要检测是否拥有钥匙，这个还好处理，关键在于你找到钥匙后就可以返回走，也就是你之前标记过走过的点又可以继续走，而且仅限于状态改变的节点，所以就去看了别人的思路，，其中一个很重要的标记方法，用一个三维数组

v\[30\]\[30\]\[1025\] 来标记，其中第三维表示每个点都有1024种状态，因为有十把钥匙，用十位二进制表示，这样就解决了如何判断当前点这个状态可不可以走。然后接下来处理存钥匙和检测钥匙开门，十把钥匙可以用十位二进制表示，1表示有改钥匙，0表示没有改钥匙，字母a,b,c,d,,,,,分别代表第1,2,3,4，，，把钥匙，即第一把钥匙表示为 1  第二把 10  第三把 100 第四把 1000  .....  所以第i把钥匙可以表示为  1<<i  ，存钥匙用到的是或运算，有1就为1没有就为0  所以存第i把钥匙为  （key为当前钥匙的状态） key=key|(1<<i), 取钥匙是与运算  取第i把钥匙为  key&(1<<i)  值为 1表示有钥匙，0位没有钥匙 所以接下来就是bfs模板！！！

AC代码：

#include<iostream>
    #include<stdio.h>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;
    
    int vis[25][25][1025]; //每个点都有1<<10种状态
    char map[25][25];
    int fx[4][2]={1,0,-1,0,0,1,0,-1};
    int n,m,t;
    
    struct nod{
        int time,key,x,y;
    };
    queue<nod>q;
    int bfs(){
        nod next,temp;
        while(!q.empty()){
            temp=q.front();
            q.pop();
            for(int i=0;i<4;i++){
                next.time=temp.time;
                next.key=temp.key;
                int h=fx[i][0]+temp.x;
                int l=fx[i][1]+temp.y;
                if(h>=0&&h<n&&l>=0&&l<m&&map[h][l]!='*'){
                    next.time++;
                    next.x=h;
                    next.y=l;
                    if(map[h][l]>='A'&&map[h][l]<='J'){
                        int aa=1<<(map[h][l]-'A');  //开门
                        if(next.key&aa&&!vis[h][l][next.key]){
                            vis[h][l][next.key]=1;
                            q.push(next);
                        }
                    }
                        else if(map[h][l]>='a'&&map[h][l]<='j'){
                            int aa=1<<(map[h][l]-'a');
                            next.key|=aa;       //装钥匙
                            if(!vis[h][l][next.key]){
                                vis[h][l][next.key]=1;
                               q.push(next);
                            }
                        }
                        else if(!vis[h][l][next.key]){
                            vis[h][l][next.key]=1;   //改状态下没有走过的点
                            q.push(next);
                        }
                        if(map[h][l]=='^'){
                            if(next.time<t)return next.time;   //找到了钥匙
                            else return -1;
                        }
                    }
                }
            }
         return -1;
    }
    
    
    int main()
    {
       while(cin>>n>>m>>t){
            while(!q.empty())q.pop();
            memset(vis,0,sizeof(vis));
            int s,t;
        for(int i=0;i<n;i++){
            scanf("%s",map[i]);
            for(int j=0;j<m;j++)
                if(map[i][j]=='@')s=i,t=j;
        }
        nod st;
        st.key=0;
        st.time=0;
        st.x=s;
        st.y=t;
        q.push(st); //起始节点
        cout<<bfs()<<endl;
       }
       return 0;
    }