力扣1162-多源BFS与多源最短路径

  |  

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

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


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

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

本文的算法要点如下:

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

$1 题目

题目链接

1162. 地图分析

题目描述

你现在手里有一份大小为 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