Nightmare
发布日期:2021-08-11 20:02:31 浏览次数:1 分类:技术文章

本文共 4517 字,大约阅读时间需要 15 分钟。

Nightmare

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 5392    Accepted Submission(s): 2673

 

Problem Description

Ignatius had a nightmare last night. He found himself in a labyrinth with a time bomb on him. The labyrinth has an exit, Ignatius should get out of the labyrinth before the bomb explodes. The initial exploding time of the bomb is set to 6 minutes. To prevent the bomb from exploding by shake, Ignatius had to move slowly, that is to move from one area to the nearest area(that is, if Ignatius stands on (x,y) now, he could only on (x+1,y), (x-1,y), (x,y+1), or (x,y-1) in the next minute) takes him 1 minute. Some area in the labyrinth contains a Bomb-Reset-Equipment. They could reset the exploding time to 6 minutes.

 

Given the layout of the labyrinth and Ignatius' start position, please tell Ignatius whether he could get out of the labyrinth, if he could, output the minimum time that he has to use to find the exit of the labyrinth, else output -1.

 

Here are some rules:

1. We can assume the labyrinth is a 2 array.
2. Each minute, Ignatius could only get to one of the nearest area, and he should not walk out of the border, of course he could not walk on a wall, too.
3. If Ignatius get to the exit when the exploding time turns to 0, he can't get out of the labyrinth.
4. If Ignatius get to the area which contains Bomb-Rest-Equipment when the exploding time turns to 0, he can't use the equipment to reset the bomb.
5. A Bomb-Reset-Equipment can be used as many times as you wish, if it is needed, Ignatius can get to any areas in the labyrinth as many times as you wish.
6. The time to reset the exploding time can be ignore, in other words, if Ignatius get to an area which contain Bomb-Rest-Equipment, and the exploding time is larger than 0, the exploding time would be reset to 6.
 

 

Input

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with two integers N and M(1<=N,Mm=8) which indicate the size of the labyrinth. Then N lines follow, each line contains M integers. The array indicates the layout of the labyrinth.
There are five integers which indicate the different type of area in the labyrinth:
0: The area is a wall, Ignatius should not walk on it.
1: The area contains nothing, Ignatius can walk on it.
2: Ignatius' start position, Ignatius starts his escape from this position.
3: The exit of the labyrinth, Ignatius' target position.
4: The area contains a Bomb-Reset-Equipment, Ignatius can delay the exploding time by walking to these areas.
 

 

Output

For each test case, if Ignatius can get out of the labyrinth, you should output the minimum time he needs, else you should just output -1.
 

 

Sample Input

3
3 3
2 1 1
1 1 0
1 1 3
4 8
2 1 1 0 1 1 1 0
1 0 4 1 1 0 4 1
1 0 0 0 0 0 0 1
1 1 1 4 1 1 1 3
5 8
1 2 1 1 1 1 1 4
1 0 0 0 1 0 0 1
1 4 1 0 1 1 0 1
1 0 0 0 0 3 0 1
1 1 4 1 1 1 1 1
 

 

Sample Output

4
-1
13
 

 

Author

Ignatius.L

分析:bfs.状态描述:坐标x,y剩余时间t.因为x,y<=8,t<=6将之表示为一个三位数.

#include
#include
#include
using namespace std;struct node{ int state; int time;};const int dx[4]={-1,1,0,0};const int dy[4]={
0,0,-1,1};node S;int N,M,map[10][10];bool f[1024];int bfs(){ queue
q; while (!q.empty()) q.pop(); memset(f,0,sizeof(f)); S.time=0; q.push(S); f[S.state]=1; while (!q.empty()) { node u=q.front(); q.pop(); int x=u.state/100,y=(u.state%100)/10,t=u.state%10; if (t==0) continue; if (map[x][y]==3) return u.time; if (t==1) continue; for (int i=0;i<4;i++) if (1<=x+dx[i] && x+dx[i]<=N && 1<=y+dy[i] && y+dy[i]<=M && map[x+dx[i]][y+dy[i]]) { int x_=x+dx[i],y_=y+dy[i]; int v=x_*100+y_*10; if (map[x_][y_]==4) v+=6; else v+=t-1; if (!f[v]) { node tmp; tmp.state=v; tmp.time=u.time+1; f[v]=1; q.push(tmp); } } } return -1;}int main(){ int T; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&M); for (int i=1;i<=N;i++) for (int j=1;j<=M;j++) { scanf("%d",&map[i][j]); if (map[i][j]==2) S.state=i*100+j*10+6; } printf("%d\n",bfs()); } return 0;}

 

转载于:https://www.cnblogs.com/dramstadt/p/3195848.html

转载地址:https://blog.csdn.net/weixin_30633949/article/details/97054970 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:spring 和 structs2 的整合
下一篇:Android - UriMatcher ContentUris

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月11日 09时07分37秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

sql 拆解函数_SQL入门50题详解(含知识点讲解及代码运行步骤拆解) 2019-04-21
java和python交互 jni_Python基于pyjnius库实现访问java类 2019-04-21
macbook pro 卸载mysql_MacBook Pro全新重装OS X Yosemite 2019-04-21
已达到计算机的连接数最大值无法再同此远程计算机连接_电脑远程访问已达到计算机的连接数最大值怎么办?解决方法很简单... 2019-04-21
mysql表名长度_JavaWeb之MySQL(一) 2019-04-21
mysql服务器语法_Mysql语法 2019-04-21
pdf 模版 汉字和数字_《吉林大学珠海学院毕业论文(设计)模板》(汉字标题版) .pdf... 2019-04-21
python bottle部署_nginx+uwsgi+bottle python服务器部署 2019-04-21
python双击py一闪_Python脚本在双击.py时无法正常运行 2019-04-21
redis logfile为空_关于Redis(二) 2019-04-21
mysql 设计两个主键都不可重复_程序员面试备战篇:18个经典MySQL面试专题解析(干货分享答案)... 2019-04-21
下列关于python2.x和3.x的区别说法正确_Python 2.x和Python 3.x版本有哪些区别?【面试题详解】... 2019-04-21
git更换_git命令 2019-04-21
hp-ux 查看系统负载_Linux性能调优 | 平均负载的理解和分析 2019-04-21
elementui的tree组件页面显示不出数据_vue路由及组件 2019-04-21
android hook sensor数据_最近,又有人在谈论Android的前景了!深入解析趋势及必备技术点... 2019-04-21
python 动态tabel的数据爬取_使用requests爬取python岗位招聘数据 2019-04-21
input js number 整数_JS基础简单小结(1) 2019-04-21
二阶差分预测后数据还原公式_xgboost系列丨xgboost原理及公式推导 2019-04-21
docker mysql服务启动失败_docker中mysql初始化及启动失败问题解决方案 2019-04-21