题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1072
/*题目大意：
某人走迷宫，从2处开始到3处终止，0是墙，1是空地。身上有定时炸弹，在第6min爆炸(只能走5步)。
4处是将定时炸弹重设的工具。问它最快能否逃出迷宫。
*/
//此题题意允许每个格子走多次,那么需要其他标记来剪枝
//我使用visited[][]保存上次访问此点用时，如果当前点比上次访问此点时间小，则走此点
#include <iostream>
#include <queue>
using namespace std;
const int MAX = 9;
int Map[MAX][MAX];
int visited[MAX][MAX];
int dir[4][2] = {{1, 0},{0, 1},{0, -1},{-1, 0}};
int time;
struct Pos {
int x, y, t, _t;//x,y表示每个节点坐标，t表示当前用时,_t表示定时炸弹显示时间
};
int main()
{
int t, n, m;
int i, j, si, sj, flag;//si,sj为起点的坐标,flag标记安全出迷宫
queue<Pos> q;
Pos v;
cin >> t;
while (t--) {
time = 0;
flag = false;
cin >> n >> m;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++) {
cin >> Map[i][j];
if (Map[i][j] == 2) {si = i; sj = j;}
visited[i][j] = 6;
}
while (!q.empty()) q.pop(); //清空队列
v.x = si; v.y = sj; v.t = 0, v._t = 0;
q.push(v);
visited[si][sj] = v._t;
while (!q.empty()) {
v = q.front();
q.pop();
if (v._t == 6) continue;//达到时间 爆炸
if (Map[v.x][v.y] == 4 && v._t != 6) v._t = 0;
if (Map[v.x][v.y] == 3) { flag = true; time = v.t; break; }
for (i = 0; i < 4; i++) {
int x = v.x + dir[i][0];
int y = v.y + dir[i][1];
if (Map[x][y] != 0 && v._t+1 < visited[x][y] && x >= 1 && x <= n && y >= 1 && y <= m)
{
Pos v1;//这里需要新建对象，不能使用前面的对象，开始我就在这里出错了
v1.x = x; v1.y = y; v1._t = v._t+1; v1.t = v.t+1;
q.push(v1);
visited[x][y] = v1._t;
}
}
}
if (flag) cout << time << endl;
else cout << "-1" << endl;
}
return 0;
}