引言
上篇我们介绍了多源BFS的相关背景知识，本篇我们将结合具体题目分析，进一步深化对于BFS算法的理解运用。
一、01矩阵
1.1 题目链接：https://leetcode.cn/problems/01-matrix/description/
1.2 题目分析：
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
1.3 思路讲解：
返回的矩阵中，原来为0的节点，保持为0即可，而原来为1的节点，则指应修改为到最近的0的距离
- 根据上篇了解的多源bfs的基础知识，我们在本题中有多个起点，即矩阵中原来为1的节点
- 与bfs求取最短路径相同，我们需要将起点入队列，但是此处可以采取
正难则反的思想，把0当作起点，求取最近的1
这是由于我们把1当作起点进行遍历时，需要统计存储多条路径，在进行比较时较为繁琐
- 由于要返回同等规模的矩阵dis，我们可以在将起点入队列时，同步将dis中相应的节点初始化为0，-1则表示尚未找到最短路径的起点
- 之后采取上下左右层序遍历的方式，记录各源点所对应的最短距离
1.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
int m=mat.size(),n=mat[0].size();
//全部初始化为-1，表示尚未计算出最短路径
vector<vector<int>> dis(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)
{
dis[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 && dis[x][y]==-1)
{
q.push({x,y});
dis[x][y]=dis[a][b]+1;//步数加1
}
}
}
return dis;
}
};
二、飞地的数量
2.1 题目链接：https://leetcode.cn/problems/number-of-enclaves/description/
2.2 题目分析：
- 给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
- 返回其中被0包围的连续1的数量（可以理解为一些相邻的1组成岛屿，被海洋包围）
- 边界上的1不能算作岛屿
2.3 思路讲解：
乍一看会感觉无从下手，找不出与多源bfs算法的关系，但如果同样采取正难则反的思想，就迎刃而解了：
- 我们把1当作起点，进行多源bfs的遍历，如果在上下左右四个方向的遍历过程中，找到了1，则说明这是一块与边界1相邻的陆地，无法形成岛屿
- 在全部遍历完成后，原数组内为1且对应标记数组为false的节点，则为一块岛屿
2.4 代码实现：
class Solution {
public:
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
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++)
{
if (grid[i][0] == 1)
{
q.push({ i,0 });
vis[i][0] = true;
}
if (grid[i][n - 1] == 1)
{
q.push({ i,n - 1 });
vis[i][n - 1] = true;
}
}
for (int j = 0; j < n; j++)
{
if (grid[0][j] == 1)
{
q.push({ 0,j });
vis[0][j] = true;
}
if (grid[m - 1][j] == 1)
{
q.push({ m - 1,j });
vis[m - 1][j] = true;
}
}
//多源bfs
while (q.size())
{
auto [a, b] = q.front();
q.pop();
vis[a][b] = true;
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])
{
q.push({ x,y });
vis[x][y] = true;
}
}
}
//统计结果
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] == false)
{
ret++;
}
}
}
return ret;
}
};
三、地图中的最高点
3.1 题目链接：https://leetcode.cn/problems/map-of-highest-peak/description/
3.2 题目分析：
- 给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由
陆地和水域单元格组成的地图。
如果 isWater[i][j] == 0 ，格子 (i, j) 是一个
陆地格子。
如果 isWater[i][j] == 1 ，格子(i, j) 是一个水域格子。
水域的高度必须为0，相邻的格子之间高度差最大为1- 要求返回一共m x n的矩阵，使得矩阵中的最高高度值最大
3.3 思路讲解：
本题与01矩阵类似，我们只需要把遍历矩阵，将所有水域入队列，之后在bfs遍历过程中，将相邻的陆地高度更新为dis[x][y]=dis[a][b]+1即可
3.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
int m=isWater.size(),n=isWater[0].size();
vector<vector<int>> dis(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]==1)
{
q.push({i,j});
dis[i][j]=0;//水域的高度为0
}
}
}
while(q.size())
{
int sz=q.size();
while(sz--)
{
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 && !isWater[x][y] && dis[x][y]==-1)//条件为不越界并且为陆地且为被遍历过
{
q.push({x,y});
dis[x][y]=dis[a][b]+1;
}
}
}
}
return dis;
}
};
四、地图分析
4.1 题目链接：https://leetcode.cn/problems/as-far-from-land-as-possible/description/
4.2 题目分析：
- 有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
- 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
- 我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
4.3 思路讲解：
- 与上题思路基本相同，采取同样策略，将海洋入队列层序遍历即可
- 注意距离的计算方式
4.4 代码实现：
class Solution {
public:
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
int m,n;
int ret=-1;//最大高度
int maxDistance(vector<vector<int>>& grid) {
m=grid.size(),n=grid[0].size();
vector<vector<int>> dis(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]==1)
{
dis[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 && grid[x][y]==0 && dis[x][y]==-1)
{
q.push({x,y});
dis[x][y]=dis[a][b]+1;
ret=max(ret,dis[x][y]);//更新高度
}
}
}
return ret;
}
};
小结
本篇关于多源bfs的介绍就暂告段落啦，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！
