多源
BFS
是指从多个源点同时进行广度优先搜索的算法。在传统的
BFS
中,我们通常从一个起始点开始,逐层遍历所有的相邻节点。而在多源
BFS
中,我们可以同时从多个源点开始,从这些源点出发,逐层向外扩展,直到达到目标或者遍历完整个图。
多源 BFS
可以用于解决一些问题,例如:
-
多个人同时逃生: 在一个迷宫中,有多个人同时被困在不同的位置,需要找到最短路径逃离迷宫。可以从这些人的位置同时开始
BFS
,第一个相遇的点就是大家逃生的最短路径。 -
多点到达目标问题: 在一些网络传播或者路由问题中,多个点需要同时到达某个目标点,可以使用多源
BFS
找到最短路径。 -
并行计算: 在一些并行计算的场景中,多源
BFS
可以用于并行地计算多个点到其他点的最短路径。
多源 BFS
的实现方式与单源 BFS
类似,只是需要同时从多个源点开始扩展。通常使用队列来进行层次遍历,每一层表示到达目标的步数。
01.矩阵
题目链接:https://leetcode.cn/problems/01-matrix/
给定一个由 0
和 1
组成的矩阵 mat
,请输出一个大小相同的矩阵,其中每一个格子是 mat
中对应位置元素到最近的 0
的距离。
两个相邻元素间的距离为 1
。
示例 1:
输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]
示例 2:
输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]]
提示:
m == mat.length
n == mat[i].length
1 <= m, n <= 104
1 <= m * n <= 104
mat[i][j] is either 0 or 1.
-
mat
中至少有一个0
思路
从 0 开始层序遍历,并且记录遍历的层数。当第一次碰到 1 的时候,当前的层数就是这个 1 离 0 的最短距离。这一种方式,在遍历的时候标记一下处理过的 1 ,能够做到只用遍历整个矩阵一次,就能得到最终结果。但是,这里有一个问题, 0 是有很多个的,我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢? 其实很简单,我们可以先把所有的 0 都放在队列中,把它们当成一个整体,每次把当前队列里面的所有元素向外扩展一次。
代码文章来源地址https://www.toymoban.com/news/detail-827425.html
class Solution{
const int dx[4]={0,0,1,-1};
const int dy[4]={-1,1,0,0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
vector<vector<int>> dist(m,vector<int>(n,-1));
queue<pair<int,int>> q;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(mat[i][j]==0){
q.push({i,j});
dist[i][j]=0;
}
while(!q.empty()){
auto [a,b]=q.front();
q.pop();
for(int i=0;i<4;++i){
int x=a+dx[i],y=b+dy[i];
if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){
dist[x][y]=dist[a][b]+1;
q.push({x,y});
}
}
}
return dist;
}
};
02.飞地的数量
题目链接:https://leetcode.cn/problems/number-of-enclaves/
给你一个大小为 m x n
的二进制矩阵 grid
,其中 0
表示一个海洋单元格、1
表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid
的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1:
输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。
示例 2:
输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 500
-
grid[i][j]
的值为0
或1
思路1
中间的1要达到边界,首先就是要有1在边界并且能够接触到,所以我们可以直接在周围一圈做单源BFS
遍历1,将它改为0,再遍历整个数组,剩下的1就是出不去的。
代码1
class Solution {
const int dx[4]={0,0,1,-1};
const int dy[4]={-1,1,0,0};
int m,n;
queue<pair<int,int>> q;
void bfs(vector<vector<int>>& grid,int i,int j){
q.push({i,j});
grid[i][j]=0;
while(!q.empty()){
int sz=q.size();
while(sz--){
auto [a,b]=q.front();
q.pop();
for(int k=0;k<4;++k){
int x=a+dx[k],y=b+dy[k];
if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
grid[x][y]=0;
q.push({x,y});
}
}
}
}
}
public:
int numEnclaves(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
for(int i=0;i<m;++i){
if(grid[i][0]==1) bfs(grid,i,0);
if(grid[i][n-1]==1) bfs(grid,i,n-1);
}
for(int i=1;i<n-1;++i){
if(grid[0][i]==1) bfs(grid,0,i);
if(grid[m-1][i]==1) bfs(grid,m-1,i);
}
int ret=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(grid[i][j]==1) ret+=1;
return ret;
}
};
思路2
使用多源BFS
同时对周边的1进行遍历
代码2
class Solution {
// 定义四个方向的坐标变化
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
public:
int numEnclaves(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
// 用于标记是否访问过的二维布尔型数组
vector<vector<bool>> vis(m, vector<bool>(n));
// 广度优先搜索的队列
queue<pair<int, int>> q;
// 1. 把边上的 1 加入到队列中
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
if (grid[i][j] == 1) {
q.push({i, j});
vis[i][j] = true;
}
// 2. 多源 BFS
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
// 如果相邻单元格是陆地且未访问过,加入队列并标记为已访问
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
vis[x][y] = true;
q.push({x, y});
}
}
}
// 3. 统计结果
int ret = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
// 统计未被包围的陆地单元格数量
if (grid[i][j] == 1 && !vis[i][j])
ret++;
return ret;
}
};
03.地图中的最高点
题目链接:https://leetcode.cn/problems/map-of-highest-peak/
给你一个大小为 m x n
的整数矩阵 isWater
,它代表了一个由 陆地 和 水域 单元格组成的地图。
- 如果
isWater[i][j] == 0
,格子(i, j)
是一个 陆地 格子。 - 如果
isWater[i][j] == 1
,格子(i, j)
是一个 水域 格子。
你需要按照如下规则给每个单元格安排高度:
- 每个格子的高度都必须是非负的。
- 如果一个格子是 水域 ,那么它的高度必须为
0
。 - 任意相邻的格子高度差 至多 为
1
。当两个格子在正东、南、西、北方向上相互紧挨着,就称它们为相邻的格子。(也就是说它们有一条公共边)
找到一种安排高度的方案,使得矩阵中的最高高度值 最大 。
请你返回一个大小为 m x n
的整数矩阵 height
,其中 height[i][j]
是格子 (i, j)
的高度。如果有多种解法,请返回 任意一个 。
示例 1:
**
**
输入:isWater = [[0,1],[0,0]]
输出:[[1,0],[2,1]]
解释:上图展示了给各个格子安排的高度。
蓝色格子是水域格,绿色格子是陆地格。
示例 2:
**
**
输入:isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出:[[1,1,0],[0,1,1],[1,2,2]]
解释:所有安排方案中,最高可行高度为 2 。
任意安排方案中,只要最高高度为 2 且符合上述规则的,都为可行方案。
思路
这一题我们要读懂题意,将原数组画出就不难发现其实和第一题矩阵的解法是一样的,同样都是使用多源BFS
来解决这个问题
代码
class Solution {
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {-1, 1, 0, 0};
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m = isWater.size(), n = isWater[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1));
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (isWater[i][j]) {
dist[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [a, b] = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
}
return dist;
}
};
- 创建一个二维矩阵
dist
,用于存储每个位置到水域的最近距离。初始化所有元素为-1。 - 创建一个队列
q
,用于进行广度优先搜索。将所有水域的位置(isWater[i][j]
为1的位置)加入队列,并将其到水域的距离设为0。 - 使用
BFS
遍历队列,不断扩展到达的位置。对于每个位置,检查其四个相邻的位置,如果相邻位置合法且未被访问过,更新其到水域的距离并将该位置加入队列。 - 最终,返回计算得到的
dist
矩阵。
04.地图分析
题目链接:https://leetcode.cn/problems/as-far-from-land-as-possible/
你现在手里有一份大小为 n x n
的 网格 grid
,上面的每个 单元格 都用 0
和 1
标记好了。其中 0
代表海洋,1
代表陆地。
请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的,并返回该距离。如果网格上只有陆地或者海洋,请返回 -1
。
我们这里说的距离是「曼哈顿距离」( Manhattan Distance):(x0, y0)
和 (x1, y1)
这两个单元格之间的距离是 |x0 - x1| + |y0 - y1|
。
示例 1:
**
**
输入:grid = [[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大,最大距离为 2。
示例 2:
**
**
输入:grid = [[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释:
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大,最大距离为 4。
提示:
n == grid.length
n == grid[i].length
1 <= n <= 100
-
grid[i][j]
不是0
就是1
思路
我们可以将每个陆地同时向海洋扩张,更新海洋到陆地的距离,最终更新的数组中最大的那个数就是最大距离,问题转化后看似是找最大距离,其实找的是最近距离,和第一题矩阵有异曲同工之妙。文章来源:https://www.toymoban.com/news/detail-827425.html
代码
class Solution {
const int dx[4]={0,0,1,-1};
const int dy[4]={-1,1,0,0};
public:
int maxDistance(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
vector<vector<int>> dist(m,vector<int>(n,-1));
queue<pair<int,int>> q;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
if(grid[i][j]){
dist[i][j]=0;
q.push({i,j});
}
int ret=-1;
while(!q.empty()){
auto [a,b] = q.front();
q.pop();
for(int i=0;i<4;i++){
int x=a+dx[i],y=b+dy[i];
if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){
dist[x][y]=dist[a][b]+1;
q.push({x,y});
ret=max(ret,dist[x][y]);
}
}
}
return ret;
}
};
到了这里,关于算法沉淀——多源 BFS(leetcode真题剖析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!