又是一道广搜题= =

这题其实和hdoj1026比较像，hdoj1026解题报告链接

但是也几经折腾才得以AC，贴一下题目原文吧:HDOJ1072 Nightmare

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.
简单来说，一个迷宫，主人公身上有一个6min后会爆炸的炸弹，每走一步1min，地图上存在炸弹重置装置可将时间重置回6min，求是否能逃出迷宫及最短逃出时间。

由于炸弹重置装置的存在，使得本题处理类似于hdoj1026，不再赘述。

说几个注意点：

1. 采用hdoj1026的方法，第一次探索到终点的时间必为最短时间，此时即可退出BFS循环；
2. 当从队列中取出一个点时，判断其剩余时间是否为1，为1则跳过（题目要求第三点第四点）；
3. 虽说题目中提到炸弹重置装置可以无限次使用，然而这是个大坑，在搜索时，应该对炸弹重置装置的点做标记，只需访问一次即可，否则如410这样的地图中，会重复4->1,1->4这样的无限循环过程进而导致超时。
   完整代码有点乱，就不贴了，参考hdoj1026即可，附上部分处理代码（java）:

   while(!que.isEmpty()){
           point a=que.poll();
           vivs[a.x][a.y]=false;
           if(a.x==ex&&a.y==ey)return;
           if(lefttime[a.x][a.y]==1)continue;
           if(reset[a.x][a.y])continue;
           if(maze[a.x][a.y]==4)reset[a.x][a.y]=true;