hdu--1429--胜利大逃亡(续) (bfs+状态压缩)

胜利大逃亡(续)

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

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

-1

 1 /*
 2      Name: hdu--1429--胜利大逃亡(续) 
 3       Copyright: ©2017 日天大帝
 4       Author: 日天大帝
 5       Date: 24/04/17 19:20
 6       Description: BFS+状态压缩，看了大神的代码，原来状态压缩是这么玩的
 7                       第一时间想的是宽搜，搜到钥匙或者中点就退出，然后将门设为路，保存步数，写的代码WA了
 8                     状态压缩 主要是开了一个三维数组，一个立体的地图，找到钥匙就开启新的一层地图
 9                     这个三维数组主要用到了位运算<<左移>>右移|运算，&预算
10                     <<:    1<<2=4;
11                     >>:       2>>1=1;
12                     |:        101|010 = 111;
13                     &        101&010 = 000; 
14                     然后就是用二进制比特串表示拥有不同钥匙的状态
15                     还得记住一点，BFS超内存的问题，将代码尽量简化，没有Wall和door这两个函数，占内存3W3
16                     直接Memory Limit Exceeded
17 */
18 #include<cstring>
19 #include<iostream>
20 #include<queue> 
21 using namespace std;
22 struct node{
23     int x,y,state;
24 }s,e;
25 const int MAX = 22;
26 char map[MAX][MAX];
27 int step[(1<<11)][MAX][MAX];
28 queue<node> q;
29 int m,n,t;
30 int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
31 bool door(int x,int y,int state){
32     if(isupper(map[x][y])){
33         int s = map[x][y] - 'A' + 1;
34         if(((1<<s) & state )!= 0)return 0;
35         else return 1;
36     }
37     return 0;
38 }
39 bool Wall(int x, int y)
40 {
41     if (x<0 || y<0 || x>=n || y>=m || map[x][y] == '*') return true;
42     return false;
43 }
44 int bfs(){
45     while(!q.empty())q.pop();
46     q.push(s);
47     while(!q.empty()) {
48         node a,temp = q.front();q.pop();
49         if(step[temp.state][temp.x][temp.y] >= t)return -1;
50         if(map[temp.x][temp.y] == '^')return step[temp.state][temp.x][temp.y];
51         for(int i=0; i<4; ++i){
52             a = temp;
53             a.x += dir[i][0];
54             a.y += dir[i][1];
55             if(Wall(a.x,a.y) ||map[a.x][a.y] == '*' ||door(a.x,a.y,a.state)
56                      ||step[a.state][a.x][a.y] != -1)continue;
57             if(islower(map[a.x][a.y])){
58                 a.state = (1<<(map[a.x][a.y] - 'a' +1) | temp.state);//
59             }
60             step[a.state][a.x][a.y] = step[temp.state][temp.x][temp.y] + 1;
61             q.push(a);
62         }
63     }
64     return -1;
65 }
66 int main(){
67     ios::sync_with_stdio(false);
68     
69     while(cin>>n>>m>>t){
70         memset(step,-1,sizeof(step));
71         int i,j;
72         for(i=0; i<n; ++i){
73             cin>>map[i];
74             for(j=0; j<m; ++j){
75                 if(map[i][j] == '@'){
76                     s.x = i;
77                     s.y = j;
78                 }
79             }
80         }
81         step[0][s.x][s.y] = 0;
82         cout<<bfs()<<endl;
83     }
84     return 0;
85 }