C++优选算法十七 多源BFS
1.单源最短路问题
一个起点一个终点。
定义：在给定加权图中，选择一个顶点作为源点，计算该源点到图中所有其他顶点的最短路径长度。
2.多源最短路问题
定义：多源最短路问题指的是在图中存在多个起点，需要求出从这些起点到图中所有其他顶点的最短路径。
3.多源BFS
用BFS解决边权为1的多源最短路问题。
解法一:
暴力解法，把多源最短路问题转化为若干个单源最短路问题。
解法二：
把所有的源点变成一个“超级源点”，问题就变成了单一的单源最短路问题。
- 把所有的起点加入到队列里面。
- 一层一层的往外扩展。
4.例题
4.1 01 矩阵
给定一个由
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]]
解法(bfs)(多个源头的最短路问题)
算法思路:
对于求的最终结果，我们有两种方式:
第一种方式:从每一个 1开始，然后通过层序遍历找到离它最近的0。
这一种方式，我们会以所有的 1 起点，来一次层序遍历，势必会遍历到很多重复的点。并且如果矩阵中只有一个 0 的话，每一次层序遍历都要遍历很多层，时间复杂度较高。
换一种方式:从 0开始层序遍历，并且记录遍历的层数。当第一次碰到1的时候，当前的层数就是这个 1 离 0 的最短距离。
这一种方式，我们在遍历的时候标记一下处理过的 1，能够做到只用遍历整个矩阵一次，就能得到最终结果。
但是，这里有一个问题，0是有很多个的，我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢?
其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。
class Solution {typedef pair<int,int> PII;int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};
public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {queue<PII> qe;int m=mat.size();int n=mat[0].size();//vv[i][j]==-1 表示没有搜索过//vv[i][j]!=-1 表示最短距离vector<vector<int>> vv(m,vector<int>(n,-1));//把所有的源点加入队列for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(mat[i][j]==0){qe.push({i,j});vv[i][j]=0;}}}//一层一层往外扩展while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){vv[x][y]=vv[a][b]+1;qe.push({x,y});}}}return vv;}
};4.2 飞地的数量
给你一个大小为
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 都在边界上或可以到达边界。
解法:
算法思路:
正难则反:
从边上的 1开始搜索，把与边上1相连的联通区域全部标记一下；
然后再遍历一遍矩阵，看看哪些位置的1没有被标记即可。
标记的时候，可以用「多源 bfs」解决。
class Solution {typedef pair<int,int> PII;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();int n=grid[0].size();queue<PII> qe;vector<vector<bool>> vv(m,vector<bool>(n,false));//将边上的1加入到队列中for(int i=0;i<m;i++){if(grid[i][0]==1)qe.push({i,0});if(grid[i][n-1]==1)qe.push({i,n-1});}for(int j=0;j<n;j++){if(grid[0][j]==1)qe.push({0,j});if(grid[m-1][j]==1)qe.push({m-1,j});}while(qe.size()){auto [a,b]=qe.front();qe.pop();vv[a][b]=true;for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&!vv[x][y]&&grid[x][y]==1){qe.push({x,y});vv[x][y]=true;}}}int count=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&vv[i][j]==false)count++;}}return count;}
};4.3 地图中的最高点
给你一个大小为
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 {typedef pair<int,int> PII;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();int n=isWater[0].size();vector<vector<int>> vv(m,vector<int>(n,-1));queue<PII> qe;//把所有的源点加入队列中for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(isWater[i][j]==1){vv[i][j]=0;qe.push({i,j});}}}while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){qe.push({x,y});vv[x][y]=vv[a][b]+1;}}}return vv;}
};4.4 地图分析
你现在手里有一份大小为
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。
解法：01矩阵的变形题，直接上多源BFS。
class Solution {typedef pair<int,int> PII;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();int n=grid[0].size();queue<PII> qe;vector<vector<int>> vv(m,vector<int>(n,-1));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){vv[i][j]=0;qe.push({i,j});}}}while(qe.size()){auto [a,b]=qe.front();qe.pop();for(int k=0;k<4;k++){int x=a+dx[k];int y=b+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&vv[x][y]==-1){qe.push({x,y});vv[x][y]=vv[a][b]+1;}}}int ret=0;for(int i=0;i<m;i++){for(int j=0;j<n;j++){ret=max(ret,vv[i][j]);}}if(ret==0)return -1;return ret;}
};