当前位置:   article > 正文

算法:BFS 解决多源最短路问题

算法:BFS 解决多源最短路问题

目录

多源最短路

题目一:矩阵

题目二:飞地的数量

题目三:地图中的最高点

题目四:地图分析


多源最短路

首先想要知道多源最短路,就先要明白单源最短路,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,就表示当前位置的最短距离

当然了此题也是可以使用这三个全局变量,这里只是说明一下,可以更简便的解题

代码如下:

  1. class Solution
  2. {
  3. public:
  4. int dx[4] = {0,0,-1,1};
  5. int dy[4] = {-1,1,0,0};
  6. vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
  7. {
  8. int m = mat.size(), n = mat[0].size();
  9. vector<vector<int>> dist(m, vector<int>(n, -1));
  10. queue<pair<int, int>> q;
  11. // 将mat中的0的位置dist该位置也改为0,并将坐标都入队列
  12. for(int i = 0; i < m; i++)
  13. {
  14. for(int j = 0; j < n; j++)
  15. {
  16. if(mat[i][j] == 0)
  17. {
  18. dist[i][j] = 0;
  19. q.push({i, j});
  20. }
  21. }
  22. }
  23. // 一层一层往外扩
  24. while(!q.empty())
  25. {
  26. // 不需要计算sz,因为dist的值就可以表示走了几步
  27. auto [a, b] = q.front();
  28. q.pop();
  29. int tmp = dist[a][b];
  30. for(int k = 0; k < 4; k++)
  31. {
  32. int x = a + dx[k];
  33. int y = b + dy[k];
  34. if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
  35. {
  36. dist[x][y] = tmp + 1;
  37. q.push({x, y});
  38. }
  39. }
  40. }
  41. return dist;
  42. }
  43. };

题目二:飞地的数量

给你一个大小为 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的个数即可

代码如下:

  1. class Solution
  2. {
  3. public:
  4. typedef pair<int, int> PII;
  5. int dx[4] = {0,0,-1,1};
  6. int dy[4] = {-1,1,0,0};
  7. bool vis[501][501];
  8. int numEnclaves(vector<vector<int>>& g)
  9. {
  10. int m = g.size(), n = g[0].size();
  11. queue<PII> q;
  12. // 将边界的1加入队列中
  13. for(int i = 0; i < m; i++)
  14. for(int j = 0; j < n; j++)
  15. if(g[i][j] == 1 && (i == 0 || i == m - 1 || j == 0 || j == n - 1))
  16. {
  17. q.push({i, j});
  18. vis[i][j] = true;
  19. }
  20. // 多源 bfs
  21. while(!q.empty())
  22. {
  23. auto [a, b] = q.front();
  24. q.pop();
  25. for(int k = 0; k < 4; k++)
  26. {
  27. int x = a + dx[k];
  28. int y = b + dy[k];
  29. if(x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 1 && vis[x][y] == false)
  30. {
  31. q.push({x, y});
  32. vis[x][y] = true;
  33. }
  34. }
  35. }
  36. // 统计结果
  37. int ret = 0;
  38. for(int i = 0; i < m; i++)
  39. for(int j = 0; j < n; j++)
  40. if(g[i][j] == 1 && vis[i][j] == false)
  41. ret++;
  42. return ret;
  43. }
  44. };

题目三:地图中的最高点

给你一个大小为 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即可,非常简单

代码如下:

  1. class Solution
  2. {
  3. public:
  4. int dx[4] = {0,0,-1,1};
  5. int dy[4] = {-1,1,0,0};
  6. typedef pair<int, int> PII;
  7. vector<vector<int>> highestPeak(vector<vector<int>>& isWater)
  8. {
  9. int m = isWater.size(), n = isWater[0].size();
  10. vector<vector<int>> height(m, vector<int>(n, -1));
  11. queue<PII> q;
  12. // 将所有源点(水域)加入队列
  13. for(int i = 0; i < m; i++)
  14. for(int j = 0; j < n; j++)
  15. if(isWater[i][j] == 1)
  16. {
  17. height[i][j] = 0;
  18. q.push({i, j});
  19. }
  20. // 多源bfs
  21. while(!q.empty())
  22. {
  23. auto [a, b] = q.front();
  24. q.pop();
  25. for(int k = 0; k < 4; k++)
  26. {
  27. int x = a + dx[k];
  28. int y = b + dy[k];
  29. if(x >= 0 && x < m && y >= 0 && y < n && height[x][y] == -1)
  30. {
  31. // 每次的高度是之前高度+1
  32. height[x][y] = height[a][b] + 1;
  33. q.push({x, y});
  34. }
  35. }
  36. }
  37. return height;
  38. }
  39. };

题目四:地图分析

你现在手里有一份大小为 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,最后返回最大的值即可

代码如下:

  1. class Solution
  2. {
  3. public:
  4. int dx[4] = {0,0,-1,1};
  5. int dy[4] = {-1,1,0,0};
  6. typedef pair<int, int> PII;
  7. int maxDistance(vector<vector<int>>& grid)
  8. {
  9. int m = grid.size(), n = grid[0].size();
  10. vector<vector<int>> dist(m, vector<int>(n, -1));
  11. queue<PII> q;
  12. for(int i = 0; i < m; i++)
  13. for(int j = 0; j < n; j++)
  14. if(grid[i][j] == 1)
  15. {
  16. dist[i][j] = 0;
  17. q.push({i, j});
  18. }
  19. int ret = -1;
  20. while(!q.empty())
  21. {
  22. auto [a, b] = q.front();
  23. q.pop();
  24. for(int k = 0; k < 4; k++)
  25. {
  26. int x = a + dx[k];
  27. int y = b + dy[k];
  28. if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1)
  29. {
  30. q.push({x, y});
  31. dist[x][y] = dist[a][b] + 1;
  32. ret = max(ret, dist[x][y]);
  33. }
  34. }
  35. }
  36. return ret;
  37. }
  38. };

BFS 解决多源最短路问题到此结束

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/946428
推荐阅读
相关标签
  

闽ICP备14008679号