【算法】BFS 系列之 多源 BFS
【ps】本篇有 4 道 leetcode OJ。
目录
一、算法简介
二、相关例题
1）01 矩阵
.1- 题目解析
.2- 代码编写
2）飞地的数量
.1- 题目解析
.2- 代码编写
3）地图中的最高点
.1- 题目解析
.2- 代码编写
4）地图分析
.1- 题目解析
.2- 代码编写
一、算法简介
最短路问题是图论中一种经典的题型，包括单源最短路、多源最短路、边权为 1 的最短路等等。本篇主要讲述的是边权为 1 的多源最短路问题。
简单来说，边权为 1 的单源最短路问题即为：求从单个起点到终点的最短路径距离，而边权为 1 的多源最短路问题即为：求从多个起点到终点的最短路径距离。
对于多源的最短路问题，我们将多个相邻的起点看作是一个整体，进而简化成一个起点，将多源转化成单源并利用 BFS 来处理，具体的方式是，在用队列进行 BFS 时，将所有起点入队，然后一层一层向外扩展。
二、相关例题
1）01 矩阵
542. 01 矩阵
.1- 题目解析
我们可以选择正难则反，不将 1 作为起点，而将 0 作为起点进行多源 BFS，去看 0 到达每个 1 的距离，从而得出最终的结果矩阵。
可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。在遍历的时候还需要标记一下处理过的 1 ，这样才能做到只遍历整个矩阵一次，具体的方式是，在创建结果矩阵之初，将矩阵元素的值全都初始化为 -1。
.2- 代码编写
class Solution {
int dx[4]={0,0,1,-1};
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));
//dist[i][j]==-1,表示没有被搜索过
//dist[i][j]!=-1,表示最短距离
queue<pair<int,int>> q;
//将所有 0 入队
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;
}
}
}
//BFS向外扩展
while(q.size())
{
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;
}
};2）飞地的数量
1020. 飞地的数量
.1- 题目解析
与上道题类似，我们也可以正难则反，从矩阵边上的 1 开始搜索，把与这些 1 相连的区域全部标记一下，然后再遍历一遍矩阵，统计哪些位置的 1 没有被标记即可，这些没有被标记的 1 就是不能到达边界的陆地。
.2- 代码编写
class Solution {
int dx[4]={0,0,1,-1};
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 全部入队
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;
}
}
}
}
//进行bfs向外扩展
while(q.size())
{
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});
}
}
}
//统计结果
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;
}
};3）地图中的最高点
1765. 地图中的最高点
.1- 题目解析
本题类似于上文的《01矩阵》，也可以选择正难则反，以水域为起点，通过 BFS 向外扩展来安排结果矩阵中每个元素的高度，使得结果矩阵中的高度（元素）之和最大。
.2- 代码编写
class Solution {
int dx[4]={0,0,1,-1};
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.size())
{
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;
}
};4）地图分析
1162. 地图分析
.1- 题目解析
本题类似于上文的《01矩阵》，曼哈顿距离其实就是最短距离，于是也可以选择正难则反，以陆地为起点，通过 BFS 向海洋去扩展。
.2- 代码编写
class Solution {
int dx[4]={0,0,1,-1};
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.size())
{
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;
}
};