题目：http://acm.hdu.edu.cn/showproblem.php?pid=1072

Problem Description

13

NightMare  就是在一个地宫中从入口到出口，2为入口，3为出口，0为墙，1为路。

当从入口离开，地宫倒计时6秒坍塌，地图中有一些装置可以重置坍塌时间，（不是坍塌时间晚6秒，而是重新更新到6秒，继续倒计时）

最终输出到出口时，花费的总时间。

有几点：

①当你踏上出口时，倒计时刚好归0，则无法出去。同理，倒计时归0时，到达重置时间点也是不可以的。

②如果出不去 输出-1.

③重置时间装置可以重复触发。

这道题目关键就在于它的VIS数组，因为里面的路可以多次访问，不能走一次都归0。

当碰到重置时间装置，使vis数组全为0，也是行不通的，因为队列里有一些其他的点的访问会影响到。

仔细，想想，什么时候不需要再次走这条路了呢？

当然是当你到达这个点时，和之前到达此点所剩余时间比较，

如果你后到达这个点剩余时间小于之前到达这个点剩余时间，那就不需要走这条路了。

剩余时间，当然是地宫坍塌的时间，如此设置vis数组，bfs就可以过了。

#include <iostream>
#include <queue>
#include <string.h>
using namespace std;

char mapp[9][9];
int vis[9][9];
int dis[4][2]={-1,0,1,0,0,-1,0,1};
int n,m,f_x,f_y;
// 坐标结构体，存储总时间，和炸弹倒计时
struct Coordinate
{
	int x,y,to_time,now_time;
};

// 判断越界等状况
bool judge(int x,int y)
{
	if(x<0 || y<0 || x>=n || y>=m)	return 0;
	if(mapp[x][y]==‘0‘)	return 0;
	return 1;
}

int bfs(int x,int y)
{
	int i;
	queue <Coordinate> q;
	Coordinate a,b;
	memset(vis,0,sizeof(vis));

	// 对队列与起点的初始化
	vis[x][y]=6;
	a.x=x;
	a.y=y;
	a.to_time=0;
	a.now_time=6;
	q.push(a);

	while(!q.empty())
	{
		a=q.front();
		q.pop();

		if(a.x==f_x && a.y==f_y)	return a.to_time;

		for(i=0;i<4;++i)
		{
			b.x=a.x+dis[i][0];
			b.y=a.y+dis[i][1];

			if(judge(b.x,b.y))
			{

				//如果踩到重置时间
				if(mapp[b.x][b.y]==‘4‘)
				{
				    if(a.now_time==1)   continue;
					b.to_time=a.to_time+1;
					b.now_time=6;
                    // 判断后到达的此点剩余时间是否 大于 之前到达这个点剩余时间
                    if(b.now_time==0 || b.now_time<=vis[b.x][b.y])	continue;
                    vis[b.x][b.y]=b.now_time;
                    q.push(b);
				}
				else
				{
					b.to_time=a.to_time+1;
					b.now_time=a.now_time-1;
					// 判断后到达的此点剩余时间是否 大于 之前到达这个点剩余时间
                    if(b.now_time==0 || b.now_time<=vis[b.x][b.y])	continue;
                    // 当然也要更新时间
                    vis[b.x][b.y]=b.now_time;
                    q.push(b);
				}
			}
		}
	}

	return -1;
}

int main()
{
	int total_case,i,j;
	int s_x,s_y;

	cin>>total_case;
	while(total_case--)
	{
		cin>>n>>m;
		// 输入时记录起点与终点坐标
		for(i=0;i<n;++i)
			for(j=0;j<m;++j)
			{
				cin>>mapp[i][j];
				if(mapp[i][j]==‘2‘)	{s_x=i;s_y=j;}
				if(mapp[i][j]==‘3‘)	{f_x=i;f_y=j;}
			}
		cout<<bfs(s_x,s_y)<<endl;
	}
	return 0;
}

ACM-BFS之Nightmare——hdu1072,布布扣,bubuko.com

ACM-BFS之Nightmare——hdu1072