广西东晋建设有限公司网站,wordpress制作插件,深圳市网站备案,企业网站建设存在的不足与困难目录
多源最短路
题目一#xff1a;矩阵
题目二#xff1a;飞地的数量
题目三#xff1a;地图中的最高点
题目四#xff1a;地图分析 多源最短路
首先想要知道多源最短路#xff0c;就先要明白单源最短路#xff0c;bfs解决单源最短路问题前面学习过#xff0c;单…目录
多源最短路
题目一矩阵
题目二飞地的数量
题目三地图中的最高点
题目四地图分析 多源最短路
首先想要知道多源最短路就先要明白单源最短路bfs解决单源最短路问题前面学习过单源最短路就是只有一个起点到终点的最短路径
多源最短路就是有若干个起点到终点的最短路径
多源bfs就是使用bfs解决多源最短路问题
这里再强调一下能够使用bfs前提必须是边权为1的问题
多源最短路问题的解决方法
解法一暴力枚举
将每一个起点都进行bfs每个起点都会获得一个结果得到的这些结果中最小的那一个就是题目所要求的
这种解答大概率是会超时的所以学习下面的解法二
解法二把所有的源点当成一个源点
此时问题就变为了单一的单源最短路问题了
在单源最短路问题中我们是把一个起点加入队列再一层一层往外扩展
而多源最短路问题中我们是把所有起点加入队列再一层一层往外扩展
其实代码都是差不多的区别就是刚开始的队列加入的起点数目不同 题目一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]] 这道题的题意就是求矩阵中每一个位置的元素的值每个位置的值是距离最近的0的距离如果本身就是0那么距离就是0
解法一每个位置挨个求
在这种解法中二维数组的每一个位置依次求离最近的0的距离很显然是会超时的所以这种解法就排除了
解法二多源BFS 正难则反
因为采用的多源bfs的策略最初的想法就是将所有的1当做一个起点去找0得到最小的距离但是当找到0后我们无法得知当前的找到的最短距离是哪个位置的1所以这种策略是不对的
那么正难则反我们可以将所有的0当做一个起点去找1这样找到的结果和上面也是一样的
那么此时当找到1后就可以将当前的最短步数直接更新到1的位置上即可
所以分为下面两步
1、把所有的0加入到队列中
遍历过程中所有0位置的数据可以直接更新为0因为自己本身就是0距离也就是0
2、一层一层向外扩展
扩展过程中需要注意已经赋过值的位置就不需要重复赋值了因为第一次赋值的一定是最短的距离
细节问题
在前面的单源最短路问题中我们使用了三个元素来解决分别是 记录是否重复出现的bool数组vis 每一次出队列的个数sz 记录扩展了step层这里的step就是最短路径了
而多源最短路问题不需要上面的三个元素只需要一个dist数组即可
因为初始化时将dist中的值全部初始化为-1然后将原始值是0的继续改为0此时再bfs过程中只要是-1的才改变它的值这里就不需要使用vis来标记了
并且我们变化是从(a,b)变为(x,y)当走到(x,y)后(x,y)的值就是(a,b)的值1所以这里也就不需要之前的sz和step了直接一个dist数组就能解决dist数组为-1就表示还没有被搜索过dist不为-1就表示当前位置的最短距离
当然了此题也是可以使用这三个全局变量这里只是说明一下可以更简便的解题
代码如下
class Solution
{
public:int dx[4] {0,0,-1,1};int dy[4] {-1,1,0,0};vectorvectorint updateMatrix(vectorvectorint mat) {int m mat.size(), n mat[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, int q;// 将mat中的0的位置dist该位置也改为0并将坐标都入队列for(int i 0; i m; i){for(int j 0; j n; j){if(mat[i][j] 0){dist[i][j] 0;q.push({i, j});}}}// 一层一层往外扩while(!q.empty()){// 不需要计算sz因为dist的值就可以表示走了几步auto [a, b] q.front();q.pop();int tmp dist[a][b];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 dist[x][y] -1){dist[x][y] tmp 1;q.push({x, y});}}}return dist; }
}; 题目二飞地的数量
给你一个大小为 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时如果发生这个1能够到达边界那么此时再遍历一遍将这个遍历过程中的所有1都做一下标记 下次就不需要遍历这些做过标记的1了这种优化可以做到不超时但是还是有些麻烦的因为需要bfs两次下面看解法二
解法二正难则反
从里面找1到边界需要考虑的事情非常多但是我可以从边界的所有1开始向里面搜索此时搜索到的1就一定是可以到达边界的
这种解法使用bfs时就可以采用多源bfs的方法将边界所有的1全部添加进队列中就可以将所有的满足条件的1全部遍历到最后再找不满足的条件的1的个数即可
代码如下
class Solution
{
public:typedef pairint, int PII; int dx[4] {0,0,-1,1};int dy[4] {-1,1,0,0};bool vis[501][501];int numEnclaves(vectorvectorint g) {int m g.size(), n g[0].size();queuePII q;// 将边界的1加入队列中for(int i 0; i m; i)for(int j 0; j n; j)if(g[i][j] 1 (i 0 || i m - 1 || j 0 || j n - 1)){q.push({i, j});vis[i][j] true;}// 多源 bfswhile(!q.empty()){auto [a, b] q.front();q.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 g[x][y] 1 vis[x][y] false){q.push({x, y});vis[x][y] true;}}}// 统计结果int ret 0;for(int i 0; i m; i)for(int j 0; j n; j)if(g[i][j] 1 vis[i][j] false)ret;return ret;}
}; 题目三地图中的最高点
给你一个大小为 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 且符合上述规则的都为可行方案。 这道题的题目描述比较长其实理解一下就是
原始矩阵的0表示陆地1表示水域需要我们返回一个新矩阵新矩阵的要求如下
①原始为水域的位置新矩阵要为0 ②其余的位置每次扩展都可以高度加1 ③求整个矩阵的最高高度值
理解完题意可以看出来也就是多源bfs从0位置开始扩展每次扩展到其他位置时都1即可非常简单
代码如下
class Solution
{
public:int dx[4] {0,0,-1,1};int dy[4] {-1,1,0,0};typedef pairint, int PII;vectorvectorint highestPeak(vectorvectorint isWater) {int m isWater.size(), n isWater[0].size();vectorvectorint height(m, vectorint(n, -1));queuePII q;// 将所有源点(水域)加入队列for(int i 0; i m; i)for(int j 0; j n; j)if(isWater[i][j] 1){height[i][j] 0;q.push({i, j});}// 多源bfswhile(!q.empty()){auto [a, b] q.front();q.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 height[x][y] -1){// 每次的高度是之前高度1height[x][y] height[a][b] 1;q.push({x, y});}}}return height;}
}; 题目四地图分析
你现在手里有一份大小为 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。 同样此题也非常简单简单分析一下
0表示海洋1表示陆地请找到海洋距离最远的陆地如果整个矩阵只有海洋或是陆地就返回-1
这道题的解法和前面几乎一模一样 找0到1的最大距离这个并不好找
我们同样正难则反找1到0的最远距离每次扩展一层就1最后返回最大的值即可
代码如下
class Solution
{
public:int dx[4] {0,0,-1,1};int dy[4] {-1,1,0,0};typedef pairint, int PII;int maxDistance(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dist(m, vectorint(n, -1));queuePII 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;while(!q.empty()){auto [a, b] q.front();q.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 dist[x][y] -1){q.push({x, y});dist[x][y] dist[a][b] 1;ret max(ret, dist[x][y]);}}}return ret;}
}; BFS 解决多源最短路问题到此结束
