hdu1429胜利大逃亡(续) (状态压缩+BFS) - c++编程基础

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每个位置都有不同钥匙的状态经过。#include
   
    
#include
    
      #include
     
       #include
      
        using namespace std; typedef struct nnn { int t,key,x,y; }NODE; int Key[25][25][1<<10],T,n,m; char map[25][25]; int abs(int x) { return x>=0 x:-x; } int bfs(int sx,int sy) { queue
       
        q; NODE now,pre; int dir[4][2]={0,1,0,-1,1,0,-1,0}; int tx,ty; now.key=0; now.t=0; now.x=sx; now.y=sy; Key[sy][sx][0]=1; q.push(now); while(!q.empty()) { pre=q.front(); q.pop(); for(int i=0; i<4; i++) { now=pre; ty=pre.y+dir[i][0]; tx=pre.x+dir[i][1]; if(ty>=0&&ty
        
         =0&&tx
         
          ='a'&&map[ty][tx]<='j'){ now.key|=(1<<(map[ty][tx]-'a')); if(Key[ty][tx][now.key]==0) Key[ty][tx][now.key]=1,q.push(now); } else if(map[ty][tx]>='A'&&map[ty][tx]<='J') { if(Key[ty][tx][now.key]==0&&(pre.key&(1<<(map[ty][tx]-'A')))) Key[ty][tx][now.key]=1, q.push(now); } else if(Key[ty][tx][now.key]==0){ Key[ty][tx][now.key]=1; q.push(now); } } } } return -1; } int main() { int sx,sy,ex,ey; while(scanf("%d%d%d",&n,&m,&T)>0) { for(int i=0; i
          
           =T) { printf("-1\n"); continue; } memset(Key,0,sizeof(Key)); printf("%d\n",bfs(sx,sy)); } }