本文共 1721 字，大约阅读时间需要 5 分钟。

这是一个很经典的好题，我想拿来分析总结

题目解析：

这题说，你从起点出发，能不能在炸弹爆炸之前走出终点？炸弹爆炸时间为6分钟，如果你能够在时间变成0之前走出去，你就胜利了！你每次只能朝着上下左右四个方向走，走一步需要1分钟，问你最短需要多久才能走出去？这里很有意思的是还有时间重置设备，如果你碰到这个设备，可以让炸弹的时间重新回到6分钟。

算法分析：

这题是问你最短需要多久，在这种不带权的图中，求最短路径，就是用bfs去做，但是这题有个6分钟的时间限制，这样与普通的最短路问题就有区别。区别在于，普通的最短路，bfs的结果一定保证是最优解，因为宽度优先，先碰到的节点一定是较快碰到的；然而，如果我们要在规定时间内去走最短路，加上有个重置装置，我们如果能够在6分钟内走出去，那么bfs的答案就是最优解，但是如果6分钟走不出去，那么就需要考虑是不是要先走到一个时间重置的装置那里去，然后再想办法走出去！

可是，这样的区别，我们该怎样去设计算法和编码呢？？

思考：

既然这个图中的点可以重复去走，那么时间重置的点是否可以重复去走呢？可以！但没必要，因为你到达一个重置点之后，往哪走都一样，如果你还回头去走那个重置点，步数必然会增加而且时间上效果没有发生变化。也就是说，如果你经过一个重置点，还是走不出去或者走不到下一个重置点，就算是你走回头路也是没用的，反之如果能走出去或者到下一个重置点，那你完全没有必要再走一遍。

Solving code：

#define _CRT_SECURE_NO_WARNINGS#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 10;int t, n, m, mp[maxn][maxn];int dir[4][2] = { {0, 1},{0, -1},{1, 0},{-1, 0} };struct Point {	int x, y, step, time;}Begin, Now, Next;int bfs() {	queue
      
        q;	q.push(Begin);	while (!q.empty()) {		Now = q.front(); q.pop();		if (1 == Now.time)	continue;		for (int i = 0; i < 4; i++) {			Next.x = Now.x + dir[i][0], Next.y = Now.y + dir[i][1];			if (Next.x >= 0 && Next.x < n && Next.y >= 0 && Next.y < m && mp[Next.x][Next.y]) {				Next.step = Now.step + 1, Next.time = Now.time - 1;				if (3 == mp[Next.x][Next.y])	return Next.step;				if (4 == mp[Next.x][Next.y]) {					Next.time = 6;					mp[Next.x][Next.y] = 0;				}				q.push(Next);			}		}	}	return -1;}int main() {	scanf("%d", &t);	while (t--) {		scanf("%d %d", &n, &m);		for (int i = 0; i < n; i++) {			for (int j = 0; j < m; j++) {				scanf("%d", &mp[i][j]);				if (2 == mp[i][j]) {					Begin.x = i, Begin.y = j;					Begin.step = 0, Begin.time = 6;				}			}		}		printf("%d\n", bfs());	}	return 0;}