算法_BFS解决多源最短路问题---持续更新
文章目录
- 前言
- 引入
- 矩阵
- 题目要求
- 题目解析
- 代码如下
- 飞地的数量
- 题目要求
- 题目解析
- 代码如下
- 地图中的最高点
- 题目要求
- 题目解析
- 代码如下
- 地图分析
- 题目要求
- 题目解析
- 代码如下
前言
本文将会向你介绍有关宽度优先搜索（BFS）解决多源最短路问题的相关题型：矩阵、飞地的数量、地图中的最高点、地图分析
引入
上一篇文章提到单源最短路问题,单源最短路问题就是给出一个起点，求到终点的最短距离，而多源最短路问题，有多个起点，求到终点的最短路径
多源BFS指的是，用BFS宽度优先搜索解决边权为1的多源最短路问题
那么该如何用BFS解决多个起点求其到终点的最短路这类问题呢？
解法一
将多源最短路问题转化为若干个单源最短路问题，即对每一个起点来一次BFS，但是这样大概率是会超时的
解法二
把所有的起点（源点）当成一个“超级源点”，问题就变成了单一的单源最短路问题
如何转化呢？
1、将所有的起点加入到队列里面
2、一层一层的往外扩展
矩阵
https://leetcode.cn/problems/2bCMpM/
题目要求
题目解析
题目要求求出每一个格子到0的最近距离，也就是求1到0的最短路，多个起点求最短路，那么这道题就是一道考察多源BFS的问题
解法一
用单源BFS的思想，即对每一个起点来一次BFS，一层层地向外扩展，这样地做法可能会超时
解法二
多源BFS，即把所有1当作一个超级源点，然后来一次BFS，可是这样也会有一个坑，当找到0后，我们需要更新1位置处的最短距离，每个“1”在遍历时都必须跟踪到最近“0”的距离，找到0后，并不是在0这个位置处标记最短距离，而是返回到1的位置处，这会使实现变得复杂
正难则反
求0到1的最短路问题，因为1到0和0到1的最短路径一定是一样的，只需要先遍历整个矩阵，将0标记出来，然后将所有0添加到队列中一层层向外扩展即可。
如图所示
模拟了一遍向外扩展的过程（绿色为第一次扩展，红色为第二次，蓝色为第三次），已经搜索标记过的区域不需要再标记
代码如下
class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> q;
vector<vector<int>> dist(mat.size(), vector<int>(mat[0].size(), -1));;
for(int i = 0; i < mat.size(); i++)
{
for(int j = 0; j < mat[0].size(); j++)
{
if(mat[i][j] == 0)
{
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];
int y = b + dy[i];
if(x >= 0 && x < mat.size() && y >= 0 && y < mat[0].size() && dist[x][y] == -1)
{
dist[x][y] = dist[a][b] + 1;
q.push({x, y});
}
}
}
return dist;
}
};
飞地的数量
https://leetcode.cn/problems/number-of-enclaves/
题目要求
题目解析
题目要求返回被 0 海洋包围的 1 岛屿的个数，如果在边界的岛屿就不算被海洋包围，可以简单地想到遍历矩阵，遇到1，就来一次bfs，找到整块岛屿，但是有个问题，就是区分不了该岛屿是不是在边界上的
证难则反
可以先将边界上的岛屿标记出来，剩下的则全部是被海洋包围的岛屿，即遍历边界上的1，遇到1，就来次bfs，找到整个岛屿并标记，然后两层for循环遍历矩阵即可
代码如下
class Solution {
public:
queue<pair<int, int>> q;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int ret = 0; //飞地的数量
//多源bfs
void bfs(vector<vector<int>>& grid)
{
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 < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1)
{
grid[x][y]++;
q.push({x, y});
}
}
}
}
int numEnclaves(vector<vector<int>>& grid)
{
for(int i = 0; i < grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 1 && (i == 0 || i == grid.size() - 1 || j == 0 || j == grid[0].size() - 1))
{
q.push({i, j});
grid[i][j]++;
}
}
}
bfs(grid);
//统计结果
for(int m = 0; m < grid.size(); m++)
{
for(int n = 0; n < grid[0].size(); n++)
{
if(grid[m][n] == 1)
{
ret++;
}
}
}
return ret;
}
};
地图中的最高点
https://leetcode.cn/problems/map-of-highest-peak/
题目要求
题目解析
设计出一种安排高度的方案，使得矩阵中的最高高度值最大1、水域的高度必须为 0
2、任意相邻的格子高度差至多为1
不要被题目所迷惑了，题目说使得矩阵的最高高度最大，如果自己设高度然后推导，这样就踩坑了，实际上从水域开始填充，可以确保陆地的高度逐步增加。这意味着距离水域更远的陆地格子将拥有更高的高度，同时还能满足要求，就能使得矩阵中的最高高度值最大
先将水域高度设置为0，将水域单元格作为一个超级源点，将所有水域单元格添加到队列中，一层层的向外扩展，每次扩展一层都比本层的高度高1
h[x][y] = h[a][b] + 1;
代码如下
class Solution {
public:
vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
{
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> q;
vector<vector<int>> h(isWater.size(), vector<int>(isWater[0].size(), -1)); //-1表示格子未被访问过
int ret = 0;
for(int i = 0; i < isWater.size(); i++)
{
for(int j = 0; j < isWater[0].size(); j++)
{
if(isWater[i][j] == 1) //将水域高度设置为0
{
h[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];
int y = b + dy[i];
if(x >= 0 && x < isWater.size() && y >= 0 && y < isWater[0].size() && h[x][y] == -1)
{
h[x][y] = h[a][b] + 1;
q.push({x, y});
}
}
}
for(int m = 0; m < grid.size(); m++)
{
for(int n = 0; n < grid[0].size(); n++)
{
ret = max(ret, h[m][n]);
}
}
}
};
地图分析
https://leetcode.cn/problems/as-far-from-land-as-possible/
题目要求
题目解析
该题题目要求求海洋单元格距离陆地单元格的最大路径距离，本质还是多源BFS问题，这里如果将海洋单元格看作一个超级源点，正向BFS是比较复杂的，当搜索到了陆地，还需要把原来出发的海洋单元格标记一下距离，正难则反，可以从陆地出发，将陆地单元格添加到队列中，一层层地向外扩展，扩展一层标记一层的距离 只需要比上一层距离多1即可，这样是比正向BFS要简单很多的 h[x][y] = h[a][b] + 1;
代码如下
class Solution {
public:
int maxDistance(vector<vector<int>>& grid)
{
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
queue<pair<int, int>> q;
int ret = -1; //如果陆地找不到海洋的话，直接返回
vector<vector<int>> h(grid.size(), vector<int>(grid[0].size(), -1)); //-1表示格子未被访问过
for(int i = 0; i < grid.size(); i++)
{
for(int j = 0; j < grid[0].size(); j++)
{
if(grid[i][j] == 1)
{
h[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];
int y = b + dy[i];
if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && h[x][y] == -1)
{
h[x][y] = h[a][b] + 1;
q.push({x, y});
ret = max(ret, h[x][y]);
}
}
}
return ret;
}
};