前言

本文将会向你介绍有关宽度优先搜索（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; //飞地的数量//多源bfsvoid 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;}
};