HDU 1429.胜利大逃亡(续)

胜利大逃亡(续)
Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
SubmitStatus Practice HDU 1429

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

总觉得上面背景里的意思和样例不一样……

这种错觉导致的问题就是，理解错了题意

最初理解的是：在t时间后传送回初始位置，但是不会死，而是继续寻路(可以在t时间内拿到钥匙，开t时间距离的门，即使钥匙距离大于t/2)

在这个错误的思路下，写出了一个错误的答案，不知道能不能“AC”

不过也算一种相似题型的思路吧

  1 /*
  2     HDU 1429.胜利大逃亡(续) 的错误理解
  3     
  4     理解为：t时间后强行传送到起点(不结束，还能继续走)
  5 */
  6 
  7 /*
  8 By:OhYee
  9 Github:OhYee
 10 Email:oyohyee@oyohyee.com
 11 Blog:http://www.cnblogs.com/ohyee/
 12 
 13 かしこいかわいい？
 14 エリーチカ！
 15 要写出来Хорошо的代码哦~
 16 */
 17 
 18 #include <cstdio>
 19 #include <algorithm>
 20 #include <cstring>
 21 #include <cmath>
 22 #include <string>
 23 #include <iostream>
 24 #include <vector>
 25 #include <list>
 26 #include <queue>
 27 #include <stack>
 28 #include <map>
 29 using namespace std;
 30 
 31 //DEBUG MODE
 32 #define debug 0
 33 
 34 //循环
 35 #define REP(n) for(int o=0;o<n;o++)
 36 
 37 
 38 const int maxn = 25;
 39 char Map[maxn][maxn];
 40 int dis[maxn][maxn];
 41 int n,m,t;
 42 typedef pair<int,int> point;
 43 const int delta[] = {1,-1,0,0};
 44 
 45 int BFS(int s1,int s2,int v1,int v2) {
 46     queue<point> Q,door;
 47     memset(dis,-1,sizeof(dis));
 48 
 49     bool key[10];
 50     memset(key,false,sizeof(key));
 51 
 52     Q.push(point(s1,s2));
 53     dis[s1][s2] = 0;
 54 
 55     while(!Q.empty() || !door.empty()) {
 56         if(!Q.empty()) {
 57             int x = Q.front().first;
 58             int y = Q.front().second;
 59             Q.pop();
 60 
 61             REP(4) {
 62                 int xx = x + delta[o];
 63                 int yy = y + delta[3 - o];
 64 
 65                 //非法访问
 66                 if(xx < 0 || xx >= n || yy < 0 || yy >= m)
 67                     continue;
 68                 //墙
 69                 if(Map[xx][yy] == '*')
 70                     continue;
 71                 //钥匙
 72                 if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
 73                     key[Map[xx][yy] - 'a'] = true;
 74                 //门
 75                 if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
 76                     if(!key[Map[xx][yy] - 'A'])
 77                         door.push(point(xx,yy));
 78 
 79                 //更新节点
 80                 int temp = dis[xx][yy];
 81                 dis[xx][yy] = (dis[xx][yy] == -1 ? dis[x][y] + 1 : min(dis[x][y] + 1,dis[xx][yy]));
 82                 //剪枝：如果已超过时间，就不再考虑
 83                 if(dis[xx][yy] >= t)
 84                     continue;
 85                 if(temp != dis[xx][yy])
 86                     Q.push(point(xx,yy));
 87             }
 88         } else {
 89             int size = door.size();
 90             bool flag = false;
 91             while(size--) {
 92                 int x = door.front().first;
 93                 int y = door.front().second;
 94                 door.pop();
 95                 if(key[Map[x][y] - 'A']) {
 96                     Q.push(point(x,y));
 97                     flag = true;
 98                     break;
 99                 }
100                 door.push(point(x,y));
101             }
102             if(flag)
103                 continue;
104             else
105                 break;
106         }
107     }
108     return dis[v1][v2];
109 }
110 
111 bool Do() {
112     if(scanf("%d%d%d",&n,&m,&t) == EOF)
113         return false;
114 
115     int s1,s2,v1,v2;
116     for(int i = 0;i < n;i++)
117         for(int j = 0;j < m;j++) {
118             scanf("
%c
",&Map[i][j]);
119             if(Map[i][j] == '@') {
120                 s1 = i;
121                 s2 = j;
122             }
123             if(Map[i][j] == '^') {
124                 v1 = i;
125                 v2 = j;
126             }
127         }
128 
129     printf("%d
",BFS(s1,s2,v1,v2));
130 
131     return true;
132 }
133 
134 int main() {
135     while(Do());
136     return 0;
137 }

不好好看样例的下场

换回正确思路，我们发现，需要保存有哪些钥匙

对于a-j 10把钥匙，我们共有1024种可能

因此，我们可以采用二进制来记录钥匙的集合

 1 //返回新的钥匙集合 
 2 //参数：原始的钥匙集合 获得的钥匙的编号
 3 inline int get_key(int key,int num) {
 4     return key | (1 << num);
 5 }
 6 
 7 //返回是否存在门的钥匙
 8 //参数：钥匙集合 门的编号
 9 inline bool has_key(int key,int num) {
10     return (key & (1 << num)) > 0;
11 }

然后看成3维空间的BFS，层数代表钥匙的集合

由于可能有1024层，因此要即时剪枝

(觉得会有更好的算法来解决吧，整个三维数组开出来有640000，略大)

另外，晚上真的不适合做题……

删错行，把if当成while找bug……

  1 /*
  2 By:OhYee
  3 Github:OhYee
  4 Email:oyohyee@oyohyee.com
  5 Blog:http://www.cnblogs.com/ohyee/
  6 
  7 かしこいかわいい？
  8 エリーチカ！
  9 要写出来Хорошо的代码哦~
 10 */
 11 
 12 #include <cstdio>
 13 #include <algorithm>
 14 #include <cstring>
 15 #include <cmath>
 16 #include <string>
 17 #include <iostream>
 18 #include <vector>
 19 #include <list>
 20 #include <queue>
 21 #include <stack>
 22 #include <map>
 23 using namespace std;
 24 
 25 //DEBUG MODE
 26 #define debug 0
 27 
 28 //循环
 29 #define REP(n) for(int o=0;o<n;o++)
 30 
 31 
 32 const int maxn = 25;
 33 char Map[maxn][maxn];
 34 int dis[maxn][maxn][1024];
 35 int n,m,t;
 36 const int delta[] = {1,-1,0,0};
 37 
 38 struct point {
 39     int x,y;
 40     int key;
 41     point(int a,int b,int c) {
 42         x = a;
 43         y = b;
 44         key = c;
 45     }
 46 };
 47 
 48 //返回新的钥匙集合 
 49 //参数：原始的钥匙集合 获得的钥匙的编号
 50 inline int get_key(int key,int num) {
 51     return key | (1 << num);
 52 }
 53 
 54 //返回是否存在门的钥匙
 55 //参数：钥匙集合 门的编号
 56 inline bool has_key(int key,int num) {
 57     return (key & (1 << num)) > 0;
 58 }
 59 
 60 
 61 int BFS(int s1,int s2,int v1,int v2) {
 62     int Min = -1;
 63     queue<point> Q;
 64     memset(dis,-1,sizeof(dis));
 65 
 66     Q.push(point(s1,s2,0));
 67     dis[s1][s2][0] = 0;
 68 
 69 
 70     while(!Q.empty()) {
 71         int x = Q.front().x;
 72         int y = Q.front().y;
 73         int key = Q.front().key;
 74         Q.pop();
 75 
 76         REP(4) {
 77             int xx = x + delta[o];
 78             int yy = y + delta[3 - o];
 79             int kk = key;
 80 
 81             //非法访问
 82             if(xx < 0 || xx >= n || yy < 0 || yy >= m)
 83                 continue;
 84             //墙
 85             if(Map[xx][yy] == '*')
 86                 continue;
 87             //钥匙
 88             if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
 89                 kk = get_key(kk,Map[xx][yy] - 'a');
 90             //门
 91             if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
 92                 if(!has_key(kk,Map[xx][yy] - 'A'))
 93                     continue;
 94 
 95             //更新节点
 96             if(dis[xx][yy][kk] == -1) {
 97                 dis[xx][yy][kk] = dis[x][y][key] + 1;
 98                 //剪枝：如果已超过时间，就不再考虑
 99                 if(dis[xx][yy][kk] >= t)
100                     continue;
101                 if(xx == v1 && yy == v2) {
102                     Min = ((Min == -1) ? dis[xx][yy][kk] : min(Min,dis[xx][yy][kk]));
103                     continue;
104                 }
105                 Q.push(point(xx,yy,kk));
106             }
107 
108         }
109     }
110 
111     return Min;
112 }
113 
114 bool Do() {
115     if(scanf("%d%d%d",&n,&m,&t) == EOF)
116         return false;
117 
118     int s1,s2,v1,v2;
119     for(int i = 0;i < n;i++)
120         for(int j = 0;j < m;j++) {
121             scanf("
%c",&Map[i][j]);
122             if(Map[i][j] == '@') {
123                 s1 = i;
124                 s2 = j;
125             }
126             if(Map[i][j] == '^') {
127                 v1 = i;
128                 v2 = j;
129             }
130         }
131 
132     printf("%d
",BFS(s1,s2,v1,v2));
133 
134     return true;
135 }
136 
137 int main() {
138     while(Do());
139     return 0;
140 }