[AcWing]844. 走迷宫（C++实现）模板题

1. 题目2. 读题（需要重点注意的东西）3. 解法4. 可能有帮助的前置习题5. 所用到的数据结构与算法思想6. 总结

1. 题目

2. 读题（需要重点注意的东西）

思路：用宽度优先搜索的思想，先将路口的节点弹出队列，然后站在该路口向前后左右四个方向看，将能走的节点加到队列中，用一个二维数组d[N][N]存储各个节点到首节点的距离。由于bfs具有最短性，因此直接输出左下角到右下角的最短的路径。

3. 解法

---------------------------------------------------解法---------------------------------------------------

#include <cstring>#include <iostream>#include <algorithm>#include <queue>using namespace std;typedef pair<int, int> PII;const int N = 110;int n, m;// 用g来存储图，d来存储各个节点到起始节点的路径int g[N][N], d[N][N];int bfs(){// 定义一个队列q来存储最新到达的地点，队首出队的时候，也是走向下一个节点的时候queue<PII> q;// 将距离d首先初始化为-1memset(d, -1, sizeof d);// 初始化起始节点的距离d[0,0] = 0d[0][0] = 0;// 将起始节点加到队列中q.push({0, 0});// 定义四个方向int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// 如果队列不为空while (q.size()){// 将队首元素赋值给tauto t = q.front();// 队首出队q.pop();// 站在这个路口，向前后左右四个方向看（这个求向左走(x-1,y)、向右走(x+1,y)、向上走(x,y-1)、向下走(x,y+1)的写法可以背下来）for (int i = 0; i < 4; i ++ ){// t为队首元素，即当前路口的x值，t.first为x轴的值，t.first + dx[i]为向左右走// t为队首元素，即当前路口的y值，t.second为y轴的值，t.second + dy[i]为向上下走int x = t.first + dx[i], y = t.second + dy[i];// 如果如果坐标（x,y）合法（在给定图的范围内）且能走（g[x][y] == 0）且没有走过（d[x][y] == -1）if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){// 将这个位置（x,y）到起始点（0,0）的距离（在上一步的距离+1（d[t.first][t.second] + 1））加到d[x][y]中d[x][y] = d[t.first][t.second] + 1;// 将这个新到达的位置加入队列q.push({x, y});}}}// 输出右下角(n-1,m-1)到起始点的距离d[n - 1][m - 1]即可// 因为bfs有最短性，所有直接输出就是左上角到右下角的最短的路径return d[n - 1][m - 1];}int main(){cin >> n >> m;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )cin >> g[i][j];cout << bfs() << endl;return 0;}

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

bfs的应用之一，需要掌握好bfs的思想是每次都把下一层能遍历的节点全部遍历一遍这个思想。

如果觉得《[AcWing]844. 走迷宫（C++实现）bfs的思想》对你有帮助，请点赞、收藏，并留下你的观点哦！