胜利大逃亡（hdu1429 bfs+状态压缩）

胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12578 Accepted Submission(s): 4570

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

Author

解题思路: 具体看代码

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <bitset>
 7 
 8 using namespace std;
 9 
10 int n,m,step,start_x,start_y,end_x,end_y;
11 int arr[25][25],vis[25][25][1<<11];
12 int door[25][25],key[25][25];
13 int fx[4][2]={1,0,-1,0,0,1,0,-1};
14 string name;
15 
16 struct Node{
17     int x,y,num,state;
18 }p;
19 
20 queue<Node> que;
21 
22 void init(){
23     memset(vis,0,sizeof(vis));
24     memset(door,0,sizeof(door));
25     memset(key,0,sizeof(key));
26     memset(arr,0,sizeof(arr));
27     while(!que.empty()) que.pop();
28 }
29 
30 int bfs(){
31     que.push({start_x,start_y,0,0});  // x,y,步数,状态
32     vis[start_x][start_y][0]=1;
33     while(!que.empty()){
34         p=que.front(),que.pop();
35         int x=p.x,y=p.y,num=p.num,state=p.state;
36         if(x==end_x&&y==end_y){
37             return num;
38         }
39         for(int i=0;i<4;i++){
40             int xx=x+fx[i][0];
41             int yy=y+fx[i][1];
42             if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&arr[xx][yy]==0){
43                 int state2=state|key[xx][yy];
44                 if(vis[xx][yy][state2]) continue; //这个坐标的这个状态访问过 就不用在访问了 步数肯定比前面长
45                 if((door[xx][yy]&state2)==door[xx][yy]){  //没有这扇门或者这扇门的钥匙已经获得了
46                     vis[xx][yy][state2]=1;
47                     que.push({xx,yy,num+1,state2});
48                 }
49 
50             }
51         }
52     }
53     return -1;
54 }
55 
56 int main(){
57     ios::sync_with_stdio(false);
58     while(cin>>n>>m>>step){
59         init();
60         for(int i=1;i<=n;i++){
61             cin>>name;
62             int len=name.size();
63             for(int j=0;j<len;j++){
64                 if(name[j]=='@') start_x=i,start_y=j+1;
65                 if(name[j]=='^') end_x=i,end_y=j+1;
66                 if(name[j]=='*') arr[i][j+1]=1;
67                 if(name[j]>='A'&&name[j]<='J'){
68                     int zhi=name[j]-'A';
69                     door[i][j+1]=(1<<zhi);   //(A-J)对应门的状态
70                 }
71                 if(name[j]>='a'&&name[j]<='j'){
72                     int zhi=name[j]-'a';
73                     key[i][j+1]=(1<<zhi);   //(a-j)钥匙的状态
74                 }
75             }
76         }
77         int flag=bfs();
78         if(flag>=step) flag=-1;
79         cout << flag << endl;
80     }
81     return 0;
82 }

View Code