算法搜索

多源BFS与多源最短路径

字数统计: 1.2k字   |   阅读时长: 4分
, ,

摘要: 力扣 1162，最基础的多源 BFS 题目

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

上个周日照例参加了力扣秋季赛的个人赛，在文章 2022力扣秋季赛个人赛战报 中记录的战报，并且把简单的第 1, 2 题过了一下。后面的 3, 4, 5 题都是有不少东西的，值得研究。

第 3 题的核心算法是多源 BFS，只是在状态的定义和转移上更复杂一些，容易误入歧途。在研究第 3 题之前，本文我们先看一个引入题 — 力扣 1162，这是一个最简单的多源 BFS 的题目，在解决本题后，再看加强版的秋季赛第 3 题就容易很多了。

本文的算法要点如下：

  • 点集到点集的最短路
  • 多源BFS

$1 题目

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

如果网格上只有陆地或者海洋，请返回 -1。

提示：

1
2
1 <= grid.length == grid[0].length <= 100
grid[i][j] 不是 0 就是 1

示例 1：
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释：
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释：
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

$2 题解

算法: 多源 BFS

这里要求的是求所有的海洋区域到陆地区域这两个点集的最短路。这个问题可以抽象成求某个点集到另一个点集中所有点的最短路 — 多源最短路。

我们知道单源最短路径的问题的算法是 dijkstra 算法，有数组和堆两种实现方法。多源最短路的实现也是在Dijkstra 的基础上做一些改动即可。具体地，堆实现的 Dijkstra 算法的第一步是源点入队，只需要把它改成将源点集合中的所有的点入队，此后的过程与 Dijkstra 的过程完全一样。

将所有源点入队后开始 Dijkstra，相当于将所有源点外面连接了一个超级源，边权为 0，然后求超级源的单源最短路。

当边的权重均为 1 时，Dijkstra 就简化为普通的 BFS 了，本题就是所有边权为 1 的简化版。

后面的问题就是源点的选择了。因为是求最长距离，所有的陆地作为起点，事先不知道最远的海洋是哪块陆地扩散到的，所以它们都要压进队，作为BFS的多个起点。

1
2
3
4
for(int i = 0; i < N; ++i)
    for(int j = 0; j < N; ++j)
        if(grid[i][j] == 1)
            q.push(PII(i, j));

把所有的陆地都入队，从所有陆地同时出发找海洋，一层一层地向海洋扩散：未选过的海洋是下一层的点。最后扩散到的海洋是离陆地最远的点。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int N = grid.size();
        using PII = pair<int, int>;
        int result = -1;
        vector<vector<bool> > visited(N, vector<bool>(N, false));
        queue<PII> q;
        for(int i = 0; i < N; ++i)
            for(int j = 0; j < N; ++j)
                if(grid[i][j] == 1)
                    q.push(PII(i, j));
        vector<PII> level_nodes;
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        while(!q.empty())
        {
            level_nodes.clear();
            ++result;
            while(!q.empty())
            {
                level_nodes.push_back(q.front());
                q.pop();
            }
            for(PII node: level_nodes)
            {
                for(int d = 0; d < 4; ++d)
                {
                    int x = node.first + dx[d];
                    int y = node.second + dy[d];
                    if(x < 0 || x >= N || y < 0 || y >= N || grid[x][y] == 1 || visited[x][y])
                        continue;
                    PII nxt(x, y);
                    q.push(nxt);
                    visited[x][y] = true;
                }
            }
        }
        if(result <= 0) return -1;
        return result;
    }
};

可以看到，与普通的 BFS 相比，多源 BFS 的改动主要在初始的时候压进了多个源点，其余的部分与常规的 BFS 一模一样。

有了本题的基础之后，下一篇文章我们来研究秋季赛的第 3 题 — 弹珠游戏。

Share