C++优选算法十七 多源BFS

1.单源最短路问题

一个起点一个终点。

定义：在给定加权图中，选择一个顶点作为源点，计算该源点到图中所有其他顶点的最短路径长度。

2.多源最短路问题

定义：多源最短路问题指的是在图中存在多个起点，需要求出从这些起点到图中所有其他顶点的最短路径。

3.多源BFS

用BFS解决边权为1的多源最短路问题。

解法一:

        暴力解法，把多源最短路问题转化为若干个单源最短路问题。

解法二：

        把所有的源点变成一个“超级源点”，问题就变成了单一的单源最短路问题。

1. 把所有的起点加入到队列里面。
2. 一层一层的往外扩展。

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;}
};