小指针

V1

2022/07/31阅读:13主题:凝夜紫

【搜索专题】看完必会的BFS解决最短路问题攻略

点击左下角“阅读原文”传送到我的博客获得更好的阅读体验。

前置知识

看完必会的搜索之超经典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的二维整数数组,数组中元素只包含01两种,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<intint> 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] = {-1010}, dy[4] = {0-101};
    int hh = 0, tt = 0;
    q[0] = {00};
    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, -1sizeof 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扩展的过程,而为什么能达到这种过程呢?

关键就在于我们的实现方式:双端队列,从队尾入队,又从队头出队这样保证了一定是第一层扩展到 的 第二层元素 放入队尾,这样就保证了 第一层完全扩展完之后 才会开始扩展第二层,以此类推,当扩展下一层的时候,当前层一定已经完全扩展完毕,这样一直扩展到最后一层,就按层遍历了所有的元素

由基本问题进行变形

以上题(走迷宫)为基础,权重相同的最短路问题又可以进行诸多扩展:

  1. 记录走过的路径;
  2. 改变连通方向;
  3. 二维矩阵变成一维数轴;
  4. 多源点BFS;
  5. 还有很多,但本文只涉及前面四个(...)

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<intint> 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-101}, dy[4] = {-1010};
    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 = {00};
    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 0 

The 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<intint> 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-11221-1-2}, dy[8] = {1221-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, -1sizeof 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。

农夫有两种移动方式:

  1. 从 X 移动到 X−1 或 X+1,每次移动花费一分钟
  2. 从 X 移动到 2∗X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。

农夫最少要花多少时间才能抓住牛?

输入格式
共一行,包含两个整数N和K。

输出格式
输出一个整数,表示抓到牛所花费的最少时间。

数据范围
0≤N,K≤105

输入样例
5 17

输出样例
4

题目描述

给出一个数轴,一个起始点N,一个终点K,已经两种移动方式,求从起点到终点的最少时间。

题目分析

本题看起来与前面的题目相差甚远,其实已经集齐了BFS最短路问题的所有要素:

  1. 从一个点走到另一个点,只是本题是在数轴上移动;
  2. 两种移动方式都是花费一分钟,即,权重相同(这点很关键);
  3. 都是求最小花费;

因此,有了这些要素,我们就可以用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, -1sizeof 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

分类:

后端

标签:

数据结构与算法

作者介绍

小指针
V1