当前位置：网站首页>【搜索专题】看完必会的BFS解决最短路问题攻略
【搜索专题】看完必会的BFS解决最短路问题攻略
2022-08-01 02:32:00 【小指针】
点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。
前置知识
看完必会的搜索之超经典flood fill问题攻略。本文所讲的题型与前置文章属于类似问题，因此需要先熟悉前置文章中「数组模拟队列」、「由坐标向其他方向扩散」等基础操作，「重复内容不会再讲」。
用BFS解决最短路问题
最短路问题是很常见的问题，而可以用BFS解决的最短路问题是其中的一个小小的子集。可以用BFS解决的最短路问题必须具备一个条件：「所有边的权重全部相等」。
从该类型问题的基础模板来研究该问题。
Wing 844. 走迷宫
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0 或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。
最初，有一个人位于左上角 (1,1) 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角 (n,m) 处，至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
「输入格式」
第一行包含两个整数 n 和 m。接下来 n 行，每行包含 m 个整数（0 或 1），表示完整的二维数组迷宫。
「输出格式」
输出一个整数，表示从左上角移动至右下角的最少移动次数。「数据范围」
1≤n,m≤100「输入样例」
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0「输出样例」
8
题目分析（BFS最短路基础问题）
给定一个n*m的二维整数数组，数组中元素只包含0和1两种，0表示路，1表示墙壁，问一个人从左上角(1,1)走到右下角(n,m)的最短路径。
题目分析
我们把两个相邻的0看做两个点，由一个0到另一个0表示可以连接一条权重为1的边，我们要求的就是从左上角0连接到右下角0的最短路径的权重之和。
由于每个边的权重都是1，所以本题自然满足条件「所有边的权重都相等」。因此，我们可以使用BFS来求出「最短路径」。
Code
整体的代码与上一篇文章看完必会的搜索之超经典flood fill问题攻略非常的相似，因此不再添加过多的注释。
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110, M = N * N;
int n, m;
int g[N][N];
PII q[M];
int d[N][N]; // dist数组存储距离
int bfs() {
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int hh = 0, tt = 0;
q[0] = {0, 0};
d[0][0] = 0;
while (hh <= tt) {
PII t = q[hh ++ ];
for (int i = 0; i < 4; i ++ ) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 or a >= n or b < 0 or b >= m) continue;
// 当点{a, b}未被搜索过 并且符合条件可以通过时 由坐标{t.x, t.y}走到{a, b}
if (d[a][b] == -1 and g[a][b] == 0) {
d[a][b] = d[t.x][t.y] + 1;
q[ ++ tt] = {a, b};
}
}
}
return d[n - 1][m - 1];
}
int main() {
memset(d, -1, sizeof d); // 初始化所有距离为-1
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;
}
（重点）BFS的搜索过程
在前文中，关于BFS的搜索模板已经给出，因此不会再重复这部分内容。
而在本文的主题是「用BFS找出最短路径」，所以这里想重点说明为什么用BFS可以搜索出最短路径。
从思路上分析
以上一道题为例，BFS的搜索过程如下图所示： 
从图中可以看到，因为BFS是以每层为单位开始扩散，所以「每次扩散都会把下一层能走到的所有点扩散到」，那么自然「每次扩散的都是当前所能到的最短路径」。
从代码上分析
如果上面的内容不能理解，没关系，我们再来从代码上看一下BFS究竟是怎么搜索的。
下图描述队列Q的变化： 
从上图中，我们可以看到BFS扩展的过程，而为什么能达到这种过程呢？
关键就在于我们的实现方式：「双端队列，从队尾入队，又从队头出队」这样保证了一定是「第一层扩展到 的 第二层元素 放入队尾，这样就保证了 第一层完全扩展完之后 才会开始扩展第二层，以此类推，当扩展下一层的时候，当前层一定已经完全扩展完毕，这样一直扩展到最后一层，就按层遍历了所有的元素」。
由基本问题进行变形
以上题（「走迷宫」）为基础，权重相同的最短路问题又可以进行诸多扩展：
记录走过的路径； 改变连通方向； 二维矩阵变成一维数轴； 多源点BFS； 还有很多，但本文只涉及前面四个（...）
AcWing 1076. 迷宫问题
给定一个 n×n 的二维数组，如下所示：
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。数据保证至少存在一条从左上角走到右下角的路径。
「输入格式」
第一行包含整数 n。接下来 n 行，每行包含 n 个整数 0 或 1，表示迷宫。
「输出格式」
输出从左上角到右下角的最短路线，如果答案不唯一，输出任意一条路径均可。按顺序，每行输出一个路径中经过的单元格的坐标，左上角坐标为 (0,0)，右下角坐标为 (n−1,n−1)。
「数据范围」
0≤n≤1000「输入样例」
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0「输出样例」
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4
题目描述
与上一题（844. 走迷宫）完全相同，只是从求「最短路径的权重总和」，变成了「输出最短路径」。
题目分析
我们知道BFS很重要的一个特性是「第一次搜索到的就是最短路径」，那我们就在第一次搜索到的时候，使用一个数组保存「路径」。
其中「路径」存储的信息是：「下一个点是由当前点扩散到的」，这样当搜索结束之后，「路径数组」保存的就是所有的转移路径。
但是这个路径存储的是「每个点是由哪个点转移过来的」，而不是「每个点可以转移到哪个点」，因此我们再倒推一遍就可以知道第一个点到最后一个点的路径。
Code
#include <iostream>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
PII q[M], path[N][N]; // path数组存储路径
int n;
bool st[N][N];
int g[N][N];
void bfs(int sx, int sy) {
// int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};
int hh = 0, tt = 0;
q[0] = {sx, sy};
st[sx][sy] = true;
while (hh <= tt) {
PII t = q[hh ++ ];
for (int i = 0; i < 4; i ++ ) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 or a >= n or b < 0 or b >= n) continue;
if (!st[a][b] and g[a][b] == 0) {
path[a][b] = t; // 点{a,b}由点t转移过来。
st[a][b] = true;
q[ ++ tt] = {a, b};
}
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
cin >> g[i][j];
bfs(n - 1, n - 1);
PII end = {0, 0};
cout << 0 << ' ' << 0 << endl;
// 倒推一遍path数组
while (end.x != n - 1 or end.y != n - 1) {
printf("%d %d\n", path[end.x][end.y].x, path[end.x][end.y].y);
// 这里为啥要缓存一下？ 如果写成这样
// end.x = path[end.x][end.y].x, end.y = path[end.x][end.y].y;
// 我们发现在更新 end.y的时候用到了end.x 而end.x在前面已经被更新了 所以要缓存一下
int x = end.x, y = end.y;
end.x = path[x][y].x, end.y = path[x][y].y;
}
return 0;
}
AcWing 188. 武士风度的牛
农民 John 有很多牛，他想交易其中一头被 Don 称为 The Knight 的牛。
这头牛有一个独一无二的超能力，在农场里像 Knight 一样地跳（就是我们熟悉的象棋中马的走法）。
虽然这头神奇的牛不能跳到树上和石头上，但是它可以在牧场上随意跳，我们把牧场用一个 x，y 的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草，给你一张地图，上面标注了 The Knight 的开始位置，树、灌木、石头以及其它障碍的位置，除此之外还有一捆草。
现在你的任务是，确定 The Knight 要想吃到草，至少需要跳多少次。
The Knight 的位置用 K 来标记，障碍的位置用 * 来标记，草的位置用 H 来标记。
这里有一个地图的例子：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . H 5 | * . . . . . . . . . 4 | . . . * . . . * . . 3 | . K . . . . . . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方（有可能其它路线的长度也是 5）：
11 | . . . . . . . . . . 10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . F< 5 | * . B . . . . . . . 4 | . . . * C . . * E . 3 | .>A . . . . D . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ---------------------- 1 0 1 2 3 4 5 6 7 8 9 0注意： 数据保证一定有解。
「输入格式」
第 1 行： 两个数，表示农场的列数 C 和行数 R。第 2..R+1 行: 每行一个由 C 个字符组成的字符串，共同描绘出牧场地图。
「输出格式」
一个整数，表示跳跃的最小次数。「数据范围」
1≤R,C≤150「输入样例」
10 11 .......... ....*..... .......... ...*.*.... .......*.. ..*..*...H *......... ...*...*.. .K........ ...*.....* ..*....*..「输出样例」
5
题目分析
给出一个二维矩阵，一个起点K，一个终点H，矩阵中 * 的点不能走，问从起点到终点的最少步数，其中一步的规则是只能走“日”字形，就像中国象棋中的“马”一样。
题目分析
又是一个求最短路径的问题，只是本题的不同点在于「扩散规则不再是像四周扩散」，而是要成“日”字型扩散，因此我们只要把扩散规则修改一下就可以了。
“日”字形扩散的坐标变化，由中心坐标可以扩展到其他八个方向，如图所示： 
把坐标中所有的横坐标和纵坐标顺时针提取出来就是：
int dx[8] = {-2,-1,1,2,2,1,-1,-2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
Code
#include <iostream>
#include <cstring>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 160, M = N * N;
PII q[M];
int n, m;
char g[N][N];
int dist[N][N];
int bfs(int sx, int sy) {
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
q[0] = {sx, sy};
int hh = 0, tt = 0;
dist[sx][sy] = 0;
while (hh <= tt) {
PII t = q[hh ++ ];
for (int i = 0; i < 8; i ++ ) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 or a >= n or b < 0 or b >= m) continue;
if (g[a][b] == '*') continue;
if (g[a][b] == 'H') return dist[t.x][t.y] + 1;
if (dist[a][b] == -1 and g[a][b] == '.') {
q[ ++ tt] = {a, b};
dist[a][b] = dist[t.x][t.y] + 1;
}
}
}
return -1;
}
int main() {
cin >> m >> n;
int sx, sy;
memset(dist, -1, sizeof dist);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ ) {
cin >> g[i][j];
// 找到源点
if (g[i][j] == 'K') sx = i, sy = j;
}
cout << bfs(sx, sy) << endl;
}
AcWing 1100. 抓住那头牛
农夫知道一头牛的位置，想要抓住它。
农夫和牛都位于数轴上，农夫起始位于点 N，牛位于点 K。
农夫有两种移动方式：
从 X 移动到 X−1 或 X+1，每次移动花费一分钟 从 X 移动到 2∗X，每次移动花费一分钟 假设牛没有意识到农夫的行动，站在原地不动。
农夫最少要花多少时间才能抓住牛？
「输入格式」
共一行，包含两个整数N和K。「输出格式」
输出一个整数，表示抓到牛所花费的最少时间。「数据范围」
0≤N,K≤105「输入样例」
5 17「输出样例」
4
题目描述
给出一个数轴，一个起始点N，一个终点K，已经两种移动方式，求从起点到终点的最少时间。
题目分析
本题看起来与前面的题目相差甚远，其实已经集齐了BFS最短路问题的所有要素：
从一个点走到另一个点，只是本题是在数轴上移动； 两种移动方式都是花费一分钟，即，权重相同（这点很关键）； 都是求最小花费；
因此，有了这些要素，我们就可以用BFS求最短路径的模型来解决这个问题。
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, k;
int q[N];
int dist[N];
int bfs() {
int hh = 0, tt = 0;
q[0] = n;
dist[n] = 0;
while (hh <= tt) {
int t = q[ hh ++ ];
// 当找到终点的时候 返回花费
if (t == k) return dist[t];
// 当前扩散到的点满足条件 并且没有被搜索过 则可以扩展
if (t - 1 >= 0 and dist[t - 1] == -1) {
dist[t - 1] = dist[t] + 1;
q[ ++ tt] = t - 1;
}
// 一个需要注意的点是，题目给出的合法的数据范围是 0~10^5
// 因此扩展到的点 只要在该范围内都是合理的。
if (t + 1 < N and dist[t + 1] == -1) {
dist[t + 1] = dist[t] + 1;
q[ ++ tt] = t + 1;
}
if (t * 2 < N and dist[t * 2] == -1) {
dist[t * 2] = dist[t] + 1;
q[ ++ tt] = t * 2;
}
}
return -1;
}
int main() {
memset(dist, -1, sizeof dist);
cin >> n >> k;
cout << bfs() << endl;
return 0;
}
AcWing 173. 矩阵距离
给定一个 N 行 M 列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：
输出一个 N 行 M 列的整数矩阵 B，其中：
「输入格式」
第一行两个整数 N,M。接下来一个 N 行 M 列的 01 矩阵，数字之间没有空格。
「输出格式」
一个 N 行 M 列的矩阵 B，相邻两个整数之间用一个空格隔开。「数据范围」
1≤N,M≤1000「输入样例」
3 4
0001
0011
0110「输出样例」
3 2 1 0
2 1 0 0
1 0 0 1
题目描述
老规矩，给出一个01矩阵，求出矩阵中每个0到距离他最近的那个1的距离，这个距离代表的是曼哈顿距离，其实就是「四连通扩散」。
题目分析
根据我们上一篇文章提到的题目，为了使「BFS第一次找到的路径就是最小路径」这个特性发挥出来，我们从1开始搜索他们到所有0的距离，这样每次找到就都是最小距离了。
因为本题说明有多个1，也就是有多个源点，因此我们可以「初始化时候，就把所有的源点都放入队列」，这样就不会有漏下的点，而当BFS结束之后，也就找到了「所有」0到离它最近的1的距离。
Code
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, M = N * N;
int n, m;
PII q[M];
int dist[N][N];
char g[N][N];
int hh, tt = -1;
void bfs() {
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
while (hh <= tt) {
PII t = q[hh ++ ];
for (int i = 0; i < 4; i ++ ) {
int a = t.x + dx[i], b = t.y + dy[i];
if (a < 0 or a >= n or b < 0 or b >= m) continue;
if (dist[a][b] == -1) {
q[ ++ tt] = {a, b};
dist[a][b] = dist[t.x][t.y] + 1;
}
}
}
}
int main()
{
cin >> n >> m;
memset(dist, -1, sizeof dist);
// 把所有的源点全部加入队列
for (int i = 0; i < n; i ++ )
for (int j = 0; j < m; j ++ ) {
cin >> g[i][j];
if (g[i][j] == '1') {
q[++ tt] = {i, j};
dist[i][j] = 0;
}
}
bfs();
for (int i = 0; i < n; i ++ ) {
for (int j = 0; j < m; j ++ )
printf("%d ", dist[i][j]);
printf("\n");
}
return 0;
}
后记
本来想添加一些LeetCode上面的题目，但是时间已经比较晚了，不想拖过12点，所以就算了吧，后续LeetCode上面的同类型题目以单张的形式每天写一篇好了，哈哈。
「END」
边栏推荐
- IDEA无法识别module(module右下角没有蓝色小方块)
- The kernel of the decompression process steps
- 机器学习初学者可以学哪些实战项目？
- RTL8762DK RTC (5)
- Chinese version of Pylint inspection rules
- Academicians of the two academies speak bluntly: Don't be superstitious about academicians
- gateway gateway cross domain
- 初出茅庐的小李第113篇博客项目笔记之机智云智能浇花器实战(2)-基础Demo实现
- IDEA does not recognize the module (there is no blue square in the lower right corner of the module)
- IDEA 找不到或无法加载主类 或 Module “*“ must not contain source root “*“ The root already belongs to module “*“
猜你喜欢
Google Earth Engine - Error resolution of Error: Image.clipToBoundsAndScale, argument 'input': Invalid type
解决IDEA默认情况下新建文件时，右击，new，没有XML文件的问题
设备树——dtb格式到struct device node结构体的转换
![[cellular automata] based on matlab interface aggregation cellular automata simulation [including Matlab source code 2004]](/img/7b/831998e19591ce8b90cfb2eefae0d4.png)
[cellular automata] based on matlab interface aggregation cellular automata simulation [including Matlab source code 2004]
Ordinary users cannot access HGFS directory
【元胞自动机】基于matlab界面聚合元胞自动机模拟【含Matlab源码 2004期】
解决安装MySQL后，Excel打开很慢的问题
The fledgling Xiao Li's 114th blog project notes: Wisdom cloud intelligent flower watering device combat (3) - basic Demo implementation
Key Points Estimation and Point Instance
纽约大学等 ｜ TM-Vec：用于快速同源检测和比对的模版建模向量
随机推荐
Device tree - conversion from dtb format to struct device node structure
大佬们，MySQL cdc source在增量过程中回收 replication slave 和 r
一个service层需要调用另两个service层获取数据，并组装成最后的数据，数据都是list，缓存如何设计？
pdb药物综合数据库
Flink deploys and submits jobs
RTL8762DK Lighting/LED (3)
/usr/sbin/vmware-authdlauncher: error while loading shared libraries: libssl.so.1.0.2*Solution
被 CSDN，伤透了心
sqlserver无法远程连接
Four ways the Metaverse is changing the way humans work
device node结构体转换成platform_device结构体
Unity3D study notes 10 - texture array
MYSQL Keyword Explain Analysis
date command
The device node structure is converted into a platform_device structure
IDEA modifies the annotation font
七月集训(第31天) —— 状态压缩
MYSQL master-slave replication
OSD read SAP CRM One Order application log way of optimization
pdb drug comprehensive database