D - 青铜一 HDU - 1429 胜利大逃亡(续) BFS-白红宇

D - 青铜一 HDU - 1429 胜利大逃亡(续) BFS

阅读量：5904 次

发布时间：2019-06-19

本文共 1785 字，大约阅读时间需要 5 分钟。

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

说是青铜题，但我觉得是这套题第四难的，可能是大佬写多了，觉得这就是一种套路的例题

BFS+状压：vis[i][j][k]记录在（i，j）拿到的钥匙状态为k 的这种状态是否遇到过

k转成二进制，变成：j....cba,a为1代表拿到了钥匙a，依次类推

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              typedef long long LL;typedef long double LD;using namespace std;const int maxn=22;char ma[maxn][maxn];int vis[maxn][maxn][1030];//int f[8][2]={ {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};int f[4][2]={ {-1,0},{1,0},{0,-1},{0,1}};int N,M,T;struct node{ int x,y; int step; int ys;};queue
              
               q;bool OK(int x,int y){ if(x>=0&&y>=0&&x
               
                
                 =T)continue; if(OK(xx,yy)&&vis[xx][yy][tem.ys]==0) { char ch=ma[xx][yy]; if(ch>='a'&&ch<='z'){ int tt=1; for(int j='a'+1;j<=ch;j++) { tt*=2; } tem.ys=tem.ys|tt; } if(ch>='A'&&ch<='Z') { int tt=tem.ys; int k=0; for(int j='A';j<=ch;j++) { k=tt%2; tt/=2; } if(k==0)continue; } q.push(tem); vis[xx][yy][tem.ys]=1; //printf("%d %d %d %c %d\n",tem.x,tem.y,tem.step,ch,vis[tem.x][tem.y]); } } } printf("-1\n");}int main(){ while(~scanf("%d%d%d",&N,&M,&T)) { memset(vis,0,sizeof(vis)); for(int i=0;i