首页 算法 搜索

# 前置知识

看完必会的搜索之超经典 flood fill 问题攻略。本文所讲的题型与前置文章属于类似问题，因此需要先熟悉前置文章中数组模拟队列、由坐标向其他方向扩散等基础操作，重复内容不会再讲。

# 用 BFS 解决最短路问题

最短路问题是很常见的问题，而可以用 BFS 解决的最短路问题是其中的一个小小的子集。可以用 BFS 解决的最短路问题必须具备一个条件：所有边的权重全部相等。

从该类型问题的基础模板来研究该问题。

# AcWing 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 扩展的过程，而为什么能达到这种过程呢？
关键就在于我们的实现方式：双端队列，从队尾入队，又从队头出队这样保证了一定是第一层扩展到 的 第二层元素 放入队尾，这样就保证了 第一层完全扩展完之后 才会开始扩展第二层，以此类推，当扩展下一层的时候，当前层一定已经完全扩展完毕，这样一直扩展到最后一层，就按层遍历了所有的元素。
# 由基本问题进行变形
以上题（走迷宫）为基础，权重相同的最短路问题又可以进行诸多扩展：
  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<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 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<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。
农夫有两种移动方式：
  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, -1, sizeof dist);
    cin >> n >> k;
    cout << bfs() << endl;
    return 0;
}
# AcWing 173. 矩阵距离
给定一个 N 行 M 列的 01 矩阵 A，A [i][j] 与 A [k][l] 之间的曼哈顿距离定义为：
dist(A[i][j],A[k][l])=∣i−k∣+∣j−l∣dist(A[i][j],A[k][l])=|i−k|+|j−l|
输出一个 N 行 M 列的整数矩阵 B，其中：
B[i][j]=min1≤x≤N,1≤y≤M,A[x][y]=1dist(A[i][j],A[x][y])B[i][j]=min_{1≤x≤N,1≤y≤M,A[x][y]=1}dist(A[i][j],A[x][y])
输入格式
第一行两个整数 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
   
 更新于   阅读次数  次
请我喝[茶]~(￣▽￣)~*
A Cat Without Sugar 微信支付
微信支付
A Cat Without Sugar 支付宝
支付宝