HDU 1429.胜利大逃亡(续)

171


题目



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”

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

/*
HDU 1429.胜利大逃亡(续) 的错误理解

理解为:t时间后强行传送到起点(不结束,还能继续走)
*/

/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)


const int maxn = 25;
char Map[maxn][maxn];
int dis[maxn][maxn];
int n,m,t;
typedef pair<int,int> point;
const int delta[] = {1,-1,0,0};

int BFS(int s1,int s2,int v1,int v2) {
queue<point> Q,door;
memset(dis,-1,sizeof(dis));

bool key[10];
memset(key,false,sizeof(key));

Q.push(point(s1,s2));
dis[s1][s2] = 0;

while(!Q.empty() || !door.empty()) {
if(!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
Q.pop();

REP(4) {
int xx = x + delta[o];
int yy = y + delta[3 - o];

//非法访问
if(xx < 0 || xx >= n || yy < 0 || yy >= m)
continue;
//墙
if(Map[xx][yy] == '*')
continue;
//钥匙
if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
key[Map[xx][yy] - 'a'] = true;
//门
if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
if(!key[Map[xx][yy] - 'A'])
door.push(point(xx,yy));

//更新节点
int temp = dis[xx][yy];
dis[xx][yy] = (dis[xx][yy] == -1 ? dis[x][y] + 1 : min(dis[x][y] + 1,dis[xx][yy]));
//剪枝:如果已超过时间,就不再考虑
if(dis[xx][yy] >= t)
continue;
if(temp != dis[xx][yy])
Q.push(point(xx,yy));
}
} else {
int size = door.size();
bool flag = false;
while(size--) {
int x = door.front().first;
int y = door.front().second;
door.pop();
if(key[Map[x][y] - 'A']) {
Q.push(point(x,y));
flag = true;
break;
}
door.push(point(x,y));
}
if(flag)
continue;
else
break;
}
}
return dis[v1][v2];
}

bool Do() {
if(scanf("%d%d%d",&n,&m,&t) == EOF)
return false;

int s1,s2,v1,v2;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++) {
scanf("\n%c\n",&Map[i][j]);
if(Map[i][j] == '@') {
s1 = i;
s2 = j;
}
if(Map[i][j] == '^') {
v1 = i;
v2 = j;
}
}

printf("%d\n",BFS(s1,s2,v1,v2));

return true;
}

int main() {
while(Do());
return 0;
}


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

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

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

//返回新的钥匙集合 
//参数:原始的钥匙集合 获得的钥匙的编号
inline int get_key(int key,int num) {
return key | (1 << num);
}

//返回是否存在门的钥匙
//参数:钥匙集合 门的编号
inline bool has_key(int key,int num) {
return (key & (1 << num)) > 0;
}


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



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

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



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

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




代码



/*
By:OhYee
Github:OhYee
Email:oyohyee@oyohyee.com
Blog:http://www.cnblogs.com/ohyee/

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
using namespace std;

//DEBUG MODE
#define debug 0

//循环
#define REP(n) for(int o=0;o<n;o++)


const int maxn = 25;
char Map[maxn][maxn];
int dis[maxn][maxn][1024];
int n,m,t;
const int delta[] = {1,-1,0,0};

struct point {
int x,y;
int key;
point(int a,int b,int c) {
x = a;
y = b;
key = c;
}
};

//返回新的钥匙集合
//参数:原始的钥匙集合 获得的钥匙的编号
inline int get_key(int key,int num) {
return key | (1 << num);
}

//返回是否存在门的钥匙
//参数:钥匙集合 门的编号
inline bool has_key(int key,int num) {
return (key & (1 << num)) > 0;
}


int BFS(int s1,int s2,int v1,int v2) {
int Min = -1;
queue<point> Q;
memset(dis,-1,sizeof(dis));

Q.push(point(s1,s2,0));
dis[s1][s2][0] = 0;


while(!Q.empty()) {
int x = Q.front().x;
int y = Q.front().y;
int key = Q.front().key;
Q.pop();

REP(4) {
int xx = x + delta[o];
int yy = y + delta[3 - o];
int kk = key;

//非法访问
if(xx < 0 || xx >= n || yy < 0 || yy >= m)
continue;
//墙
if(Map[xx][yy] == '*')
continue;
//钥匙
if(Map[xx][yy] >= 'a' && Map[xx][yy] <= 'j')
kk = get_key(kk,Map[xx][yy] - 'a');
//门
if(Map[xx][yy] >= 'A' && Map[xx][yy] <= 'J')
if(!has_key(kk,Map[xx][yy] - 'A'))
continue;

//更新节点
if(dis[xx][yy][kk] == -1) {
dis[xx][yy][kk] = dis[x][y][key] + 1;
//剪枝:如果已超过时间,就不再考虑
if(dis[xx][yy][kk] >= t)
continue;
if(xx == v1 && yy == v2) {
Min = ((Min == -1) ? dis[xx][yy][kk] : min(Min,dis[xx][yy][kk]));
continue;
}
Q.push(point(xx,yy,kk));
}

}
}

return Min;
}

bool Do() {
if(scanf("%d%d%d",&n,&m,&t) == EOF)
return false;

int s1,s2,v1,v2;
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++) {
scanf("\n%c",&Map[i][j]);
if(Map[i][j] == '@') {
s1 = i;
s2 = j;
}
if(Map[i][j] == '^') {
v1 = i;
v2 = j;
}
}

printf("%d\n",BFS(s1,s2,v1,v2));

return true;
}

int main() {
while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论