公司网站首页的图片怎么做,廊坊住房和城乡建设厅网站,知更鸟wordpress设置注册,互联网营销师题库及答案文章目录 前言那么什么是单源最短路 / 多源最短路呢#xff1f;如何解决此类题#xff1f;解法一解法二对于解法二#xff0c;如何编写代码#xff1f; 算法题542.01矩阵1020.飞地的数量1765.地图中的最高点1162.地图分析 前言
此前我们对 单源最短路 问题进行的讲解… 文章目录 前言那么什么是单源最短路 / 多源最短路呢如何解决此类题解法一解法二对于解法二如何编写代码 算法题542.01矩阵1020.飞地的数量1765.地图中的最高点1162.地图分析 前言
此前我们对 单源最短路 问题进行的讲解 使用bfs算法解决单源最短路问题 那么什么是单源最短路 / 多源最短路呢
画图来说单源最短路问题即为 而对于多源最短路问题: 如何解决此类题
自然是 利用BFS算法解决下面提出解法
解法一 解法二 当我们将所有的源点作为一个源点来进行解题时问题又变成了单源最短路问题而为什么可以认为这种解法是正确的呢? 感性的理解 对于上图的ABC三点显然A点到目标点的距离更远当我们将其作为一个点时A点就会被直接排除此时该特殊源点实际上就是最近的源点的合并。 对于解法二如何编写代码
我们对于 单源最短路 问题的bfs解法为
将起始点加入到队列中再进行一层一层的扩展
自然对于 多源最短路 的bfs解法为
将所有的起始点加入到队列中再进行一层一层的扩展 算法题
542.01矩阵 思路
题意分析题目要求返回一个数组该数组的每一位都是矩阵中当前位置到最近的0的距离。这个数组我们叫做dist数组下面多道题都会用上解法一 对每个位置都进行扩展 解法二 bfs 正难则反 dist数组 正难则反将思维逆转我们以0作为起点对矩阵进行扩容dist数组也是结果数组开始初始化为-1对于dist[i][j] dist[i][j] -1未被检索过dist[i][j] ! -1该位置到0的最短距离 将矩阵的所有起始点0的位置加入矩阵根据下图的思路每次对队列中的元素进行扩展
代码
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)); // 将dist数组元素初始化为-1(未检索的状态)queuepairint, int q;// 正难则反以矩阵中的0作为起点进行扩展// 将所有起始点入队for(int i 0; i m; i)for(int j 0; j n; j)if(mat[i][j] 0){q.push({i, j});dist[i][j] 0;}// 对队列中的元素进行拓展while(q.size()){auto [a, b] q.front(); q.pop();for(int i 0; i 4; i){int x dx[i] a, y dy[i] b;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;}
};1020.飞地的数量 思路
题意分析题目要求返回无法离开水域的陆地单元格个数即在边界内且被水域完全包裹的单元格。解法 bfs 正难则反 正难则反我们以四边的1为起点向内扩展多源bfs将四边的1作为起点入队将相连接的陆地单元格标记最后遍历visited数组统计结果
代码
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int numEnclaves(vectorvectorint grid) {int m grid.size(), n grid[0].size();// 将visited数组元素初始化为0vectorvectorbool visited(m, vectorbool(n, false));queuepairint, int q;// 正难则反以边界的1为起始点进行bfs// 1. 找到边界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)) grid[i][j] 1){q.push({i, j});visited[i][j] true;}// 2. 多源bfswhile(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) !visited[x][y] grid[x][y]){q.push({x, y});visited[x][y] true;}}}// 3. 提取结果int ret 0;for(int i 0; i m; i)for(int j 0; j n; j)if(!visited[i][j] grid[i][j])ret;return ret;}
};1765.地图中的最高点 思路
题意分析题目给出一个矩阵1为水域0为陆地要求我们自行安排陆地高度使矩阵的最高高度最大相邻单元格高度差 1解法 bfs dist数组 思路 首先创建dist数组原理与第一题01矩阵一样将矩阵中所有水域的位置在dist中初始化为0并插入到队列中。由于要求矩阵的最高高度最大我们在设计高度时自然要将高度差都设为最大值即1随后进行多源bfs的操作综上我们发现这道题理清思路后代码方面和“01矩阵”完全一致
代码
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};vectorvectorint highestPeak(vectorvectorint isWater) {// 思路同 “10矩阵”int m isWater.size(), n isWater[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, int q;// 1.对水域进行扩展for(int i 0; i m; i)for(int j 0; j n; j)if(isWater[i][j] 1) // 1是水域{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){q.push({x, y});dist[x][y] dist[a][b] 1;}}}return dist;}
};1162.地图分析 思路 题意分析题目要求找到离陆地最远的海洋单元格的曼哈顿距离 曼哈顿距离 简单解释为 解法思路 bfs 正难则反 dist数组 正难则反题目要求找海洋到陆地的最大距离我们以陆地单元格作为起始点向内扩展同样的思路我们首先遍历数组将陆地单元格位置存入到队列中并标记dist的位置后执行多源bfs的代码思路即可
代码
class Solution {
public:int dx[4] {0, 0, -1, 1};int dy[4] {-1, 1, 0, 0};int maxDistance(vectorvectorint grid) {int m grid.size(), n grid[0].size();// 正难则反以1为起点向内扩展并标记vectorvectorint dist(m, vectorint(n, -1));queuepairint, int q;// 1. 根据单元格1向内扩展for(int i 0; i m; i)for(int j 0; j n; j)if(grid[i][j] 1){q.push({i, j});dist[i][j] 0;}// 2. 多源bfsint ret -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){q.push({x, y});dist[x][y] dist[a][b] 1;ret max(ret, dist[x][y]);}}}return ret;}
};
