深度解析之算法之多源BFS
花莲强震大陆网友吁募捐助台渡难关 台媒：感受到浓浓的爱
多源BFS：用BFS解决边权为1的多源最短路问题 解法一：暴力，将多源最短路问题转换为若干个单源最短路问题，但是肯定是会出现超时现象的 解法二：把所有的源点当成一个超级源点，问题就变成了单体的单源最短路问题了
87.矩阵
题目链接
给定一个由 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] ]
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.mat中至少有一个0
就是返回一个数组，数组的内容就是当前这个点到附近最近0的距离
将所有的0当成起点，1当成终点 1.把所有的0位置加入到队列中 2,。一层一层的向外拓展即可
class Solution
{
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
int m=mat.size(),n=mat[0].size();
//dist[i][j]==-1的话没救说明这个数是没有被搜索过的
//dist[i][j]!=-1 表示的是最短距离
vector<vector<int>>dist(m,vector<int>(n,-1));//初始化为-1
queue<pair<int,int>>q;
//1.将所有的源点加入到队列中去，这里源点是0
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(mat[i][j]==0)//说明我们的这个0是源点，那么我们加入到队列中去
{
q.push({i,j});
dist[i][j]=0;//标记下我们当前的坐标是否遍历过
}
}
}
//2.一层一层的往外扩
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 &&dist[x][y]==-1)//没有被搜索过的坐标
{
dist[x][y]=dist[a][b]+1;//我们这里直接+1就行了，因为我们的dist[a][b]存的即是最短距离
q.push({x,y});
}
}
}
return dist;
}
};88.飞地的数量
题目链接
给你一个大小为 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 都在边界上或可以到达边界。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j]的值为0或1
我们直接正难则反 先找到边界的1，然后一层一层的向内走
class Solution
{
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(),n=grid[0].size();
vector<vector<bool>>vis(m,vector<bool>(n));//vis这个数组是来检查这个坐标是否被遍历过
queue<pair<int,int>>q;
//将四周的1加入到队列中去
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0||i==m-1||j==0||j==n-1)//当这四个条件随便一个成立的时候都说明我们到了边界了
{
if(grid[i][j]==1)//说明我们找到了边界上的1，那么我们将这个1加进队列中去
q.push({i,j});
vis[i][j]=true;
}
}
}
//多源bfs,向内进行扩展操作
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&&vis[x][y]==false&&grid[x][y]==1)//这个位置的值必须是1，并且是没有遍历过的
{
vis[x][y]=true;//将这个位置状态进行标记一下
q.push({x,y});//将这个位置插入到队列中去
}
}
}
//统计结果
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)//这个位置是1，并且这个位置没有被标记过状态的话,说明就是我们想要的那种位置
{
ret++;
}
}
}
return ret;
}
};先利用两个for循环将四周的1加入到我们的队列中去
然后把利用多源bfs向内进行拓展操作
最后我们利用两层循环将我们的整个区域进行遍历一遍，然后如果这个位置是没有被标记过状态的话，并且这个位置的值的大小是1的话，那么我们就将这个算进去，ret++
89.地图中的最高点
题目链接
给你一个大小为 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 且符合上述规则的，都为可行方案。
提示：
m == isWater.lengthn == isWater[i].length1 <= m, n <= 1000isWater[i][j]要么是0，要么是1。- 至少有 1 个水域格子。
注意： 本题与 542 题相同。
我们将0周围的拓展成1，再将1周围的拓展成2
class Solution
{
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(),n=isWater[0].size();
vector<vector<int>>dist(m,vector<int>(n,-1));//将里面的元素都初始化为-1，如果这个位置的值是-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)//说明这个位置是水域
{
dist[i][j]=0;//那么我们将这个区域标记为0
q.push({i,j});//将这个位置加入到（i,j）中去
}
}
}
//2.多源bfs
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&&dist[x][y]==-1)//这个位置是没有搜索过的
{
dist[x][y]=dist[a][b]+1;//这个大小直接在上一层的坐标的基础上加上一
q.push({x,y});//将当前的坐标放进队列中去
}
}
}
return dist;
}
};90.地图分析
题目链接你现在手里有一份大小为 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。
提示：
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]不是0就是1
class Solution
{
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(),n=grid[0].size();
vector<vector<int>>dist(m,vector<int>(n,-1));//里面的值是-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)
{
dist[i][j]=0;//标记下这个位置的状态
q.push({i,j});//将坐标插入到队列中去
}
}
}
int ret=-1;//统计最终的结果，一开始初始化为-1，因为如果找不到的话，那么就返回-1
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&&dist[x][y]==-1)//说明这个位置是没有遍历过的
{
dist[x][y]=dist[a][b]+1;
q.push({x,y});
ret=max(ret,dist[x][y]);
}
}
}
return ret;
}
};腾讯云开发者
