本题使用基本的广度优先搜索。
#include <iostream> #include <queue> using namespace std; int T, N, M; int labyrinth[10][10]; //迷宫地图 int direction[4][2] = { { 0, 1 }, { 0, -1 }, { -1, 0 }, { 1, 0 } }; //方向 struct node //地图中的点 { int etime; //剩余时间 int x, y; //坐标 int totalTime; //总用时 }; int BFS(int sx, int sy); //广度优先搜索 int main() { cin >> T; while (T--) { memset(labyrinth, 0, sizeof(labyrinth)); cin >> N >> M; int sx, sy; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { cin >> labyrinth[i][j]; if (labyrinth[i][j] == 2) //起始坐标 { sx = i; sy = j; } } } int result = BFS(sx, sy); cout << result << endl; } return 0; } int BFS(int sx, int sy) //广度优先搜索 { queue<node> q; while (!q.empty()) //清空队列（初始化） { q.pop(); } node start, temp; //当前节点，暂存节点 start.x = sx; start.y = sy; start.etime = 6; start.totalTime = 0; q.push(start); while (!q.empty()) { temp = q.front(); q.pop(); if (labyrinth[temp.x][temp.y] == 3) //出口 return temp.totalTime; if (temp.etime == 1) //炸弹爆炸 continue; int tx, ty; for (int i = 0; i < 4; i++) //广度搜索 { tx = temp.x + direction[i][0]; ty = temp.y + direction[i][1]; if (tx < 1 || tx > N || ty < 1 || ty > M || labyrinth[tx][ty] == 0) //越界或撞墙 continue; start.x = tx; start.y = ty; start.etime = temp.etime - 1; start.totalTime = temp.totalTime + 1; if (labyrinth[tx][ty] == 4) //时间重置，走过一次之后不再重复走 { start.etime = 6; labyrinth[tx][ty] = 0; } q.push(start); } } return -1; }继续加油。
