hdu 1072 Nightmare BFS,第一次刷BFS的题,感好牛逼的。。。_Lionel_D的博客-程序员信息网

技术标签: 广搜  hdu1072  搜索  ACM  Nightmare  数据结构  BFS  

Nightmare

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7758    Accepted Submission(s): 3723


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
我不想解释了太多了,http://blog.csdn.net/guodongxiaren/article/details/23552313
有大牛写了,我是照着他的写的,代码雷同度到达百分之九十~~~我还在成长中~~~~
代码:
<pre name="code" class="cpp">#include <cstdio>
#include <queue>
#include <cstring>

using namespace std ;
int map[10][10] , rest[10][10] , spend[10][10] , ans = -1;
int dir[4][2] = {1,0,-1,0,0,1,0,-1} ;
int n , m ;	//列与行 
queue<int> q;

bool judge(int x ,int y , int time)
{
	if(x<0||x>=n || y<0||y>=m) //坐标越界检查 
	{
		return false ;
	}
	if(map[x][y] == 0 || rest[x][y]>=time)//位置合理判断 
	{
		return false ;
	}
	return true ;
}

void BFS(int des)
{
	q.push(des) ;
	while(!q.empty())
	{
		int des = q.front();
		q.pop() ;
		int x = des/10 , y = des%10 ;
		if(rest[x][y] == 0)
			continue ;
		if(map[x][y] == 3)
		{
			if(ans == -1 || spend[x][y]<ans)
			{
				ans = spend[x][y] ;
			}
			continue ;
		}
		if(map[x][y] == 4)
		{
			rest[x][y] = 6 ;
			map[x][y] = 0 ;
		}
		for(int k = 0 ; k < 4 ; ++k)
		{
			int nextX = x + dir[k][0];
			int nextY = y + dir[k][1];
			if(judge(nextX,nextY,rest[x][y]-1))
			{
				q.push(nextX*10+nextY);
				rest[nextX][nextY] = rest[x][y]-1 ;
				spend[nextX][nextY] = spend[x][y]+1;
			}
		}
	}
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int des ;
		scanf("%d%d",&n,&m);
		memset(map,0,sizeof(map));
		memset(spend,0,sizeof(spend));
		memset(rest,0,sizeof(rest));
		for(int i = 0 ; i < n ; ++i)
		{
			for(int j = 0 ; j < m ; ++j)
			{
				scanf("%d",&map[i][j]);
				if(map[i][j] == 2)
				{
					rest[i][j] = 6 ;
					des = i*10 + j ;
				}
			}
		}
		
		ans = -1 ;
		BFS(des);
		printf("%d\n",ans) ;
	}
	return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Lionel_D/article/details/43770021

智能推荐

nginx lua连接mysql_nginx-lua-mysql 使用简介_凡仕咖啡的博客-程序员信息网

需要安装Nginx安装Nginx的echo模块安装Nginx的lua 模块安装Mysqlps: echo模块,可以让我们像在PHP使用echo一样,打印出参数。但是要加 default_type "text/html”;不然会出现请求页面出现下载的情况。知识点:Nginx操作命令,-s [reload|stop]安装完lua以后,需要安装luajit;使用luajit 的luarocks类似于PH...

安装cenos7(保姆级教程,可对照着安装)_杰之行的博客-程序员信息网_cenos7

一、安装Cenos7前的基本配置1. 创建新的虚拟机2.推荐自定义,下一步3.默认操作,下一步4.选择好Linux和cenos7,下一步5.定义虚拟机名称和安装位置(推荐全英文),下一步6.根据自己电脑实际情况选择(不要纠结),下一步7.根据自己电脑实际情况选择(不要纠结),下一步8.默认选择,下一步9.默认选择,下一步10.默认选择,下一步11.推荐选择第一个,下一步12.推荐自己抠门一点(不要一下子分配很多,浪费),下一步13.选择虚拟磁盘安装位置,下一

PostMan请求接口--无响应解决案例(Could not get any response)[email protected]大壮的博客-程序员信息网_postman发送请求后端无反应

声明:本次问题涉及到的接口为公司内部接口,所以敏感处做了打码处理Postman作为接口测试常用工具之一,做开发和测试的同学肯定都会或多或少的使用,使用过程中难免会遇到一些问题,今天来记录一下请求接口无响应的问题:案例如下:接口为GET请求,应该传递的参数也都按照接口文档进行了配置,包括请求前做的加密处理,也都通过代码前置进行了处理,在本地和网站这个接口都是可以请求成功,但是放在了postman就不行了;解决方式:我在网上翻译了一下请求结果,大概就是告诉我问题出在了“SSL证书”相关的方面接下

myeclipse 2017 ci 10 破解_wsyzxss的博客-程序员信息网

https://blog.csdn.net/weixin_42539046/article/details/80800213 本文介绍MyEclipse 2017 CI 7、CI 8、CI 9和CI 10的安装与激活。此方法理论上应该能激活MyEclipse 2017 CI所有系列,即激活方法是通用的,只是激活文件略有不同。本文提供MyEclipse 2017 CI 7、CI 8、CI...

S7-1500 CPU 和显示屏的固件更新说明_zhoulibo0922的博客-程序员信息网

1、通过 STEP 7 (TIA-Portal) 进行在线固件更新;2、使用 SIMATIC 存储卡卡进行离线固件更新 (STEP 7、TIA-Portal)

[Linq]LINQ的左连接、右连接、内连接_厦门德仔的博客-程序员信息网_c# linq 左连接

1、左连接:var LeftJoin = from emp in ListOfEmployeesjoin dept in ListOfDepartmenton emp.DeptID equals dept.ID into JoinedEmpDeptfrom dept in JoinedEmpDept.DefaultIfEmpty()select new {EmployeeName = emp.Name,DepartmentName = dept

随便推点

使用ESP8266构建一个简单的温湿度在线监测装置_gitdive的博客-程序员信息网_esp8266测温

主要功能在终端对环境温湿度进行采集,通过WIFI接入网络能够显示实时参数变化(表格和曲线),具备一定的历史数据回溯功能后期可加入一些联动控制或报警功能项目目的没有什么特别的实用性,就是随便玩一玩,建立基础的物联网概念开展思路采集端每两秒采集一次数据并传输,数据传输可采用post或websocket,后续考虑直接采用websocket服务器端实时接受采集的数据并进行显示,每十分钟对数据进行一次存储,作为历史数据(后面这个还没搞。。。)服务器搭建选择网络连接可以采用虚拟服务器进行内网映射

DMP项目_柒~~的博客-程序员信息网_dmp项目

DMP说明:DMP(Data Management Platform)数据管理平台,是把分散的多方数据进行整合纳入统一的技术平台,并对这些数据进行标准化和细分,让用户可以把这些细分结果推向现有的互动营销环境里的平台。1.项目背景互联网广告(本项目针对手机,OTT,PC)的崛起得益于信息技术的发展和普及,智能的终端设备迅猛的发展。互联网广告的优势:1)受众多 6-7亿网民2)可以跟踪用户...

手机APP安装包缩减方案_腾讯移动品质中心TMQ的博客-程序员信息网

安装包大小对于产品很重要主要有如下几个原因:1、手机APP安装包的大小会影响用户是否愿意花费流量来下载此APP;2、包体越大下载过程越长,用户取消下载的可能性越大;3、在手机空间不足,用户需要清理手机空间时,包体越大的软件被清理的可能性越大;4、一些预装软件,合作厂商会限定软件大小;5、APP经过多次版本迭代,产生不少冗余代码和无用资源,会带来更高的学习和维护成本,也更容易出错。文章将分三

顺藤摸瓜RocketMQ之刷盘机制debug解析_jianjun_fei的博客-程序员信息网

Rocketmq 刷盘机制三个文件在rocketmq里面存在这样三个文件indexfileconsumequeuecommitlog其中indexfile和consumequeue可以理解为索引文件,indexFileconsumeQueuecommitlog刷盘

kali工具之Beef_wulanlin的博客-程序员信息网

*本工具仅供技术分享、交流讨论,严禁用于非法用途。简介Browser Exploitation Framework(BeEF) BeEF是日前最强大的浏览器开源渗透测试框架,通过X55漏洞配合JS脚本和 Metasploit进行渗透; BeEF是基于Ruby语言编写的,并且支持图形化界面,操作简单主要功能信息收集:1.网络发现2.主机信息3.Cookie获取4.会话劫持5.键盘记录6.插件信息持久化控制:1.确认弹框2.小窗口3.中间人社会工程:1

linux的traceroute命令详解_雪域白狼的博客-程序员信息网_traceroute6

traceroute命令详解traceroute [-46dFITUnrAV] [-f first_ttl] [-g gate,...]        [-i device] [-m max_ttl] [-p port] [-s src_addr]        [-q nqueries] [-N squeries] [-t tos]        [-l flow_label] [-w wait...

推荐文章

热门文章

相关标签