2021百度最新收录方法,优化方案2022版,宜春网站建设推广,公司网站建设怎么规划比较好算法沉淀——多源 BFS#xff08;leetcode真题剖析#xff09; 01.矩阵02.飞地的数量03.地图中的最高点04.地图分析 多源
BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的
BFS 中#xff0c;我们通常从一个起始点开始#xff0c;逐层遍历所有的相邻节点。而在多… 算法沉淀——多源 BFSleetcode真题剖析 01.矩阵02.飞地的数量03.地图中的最高点04.地图分析 多源
BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的
BFS 中我们通常从一个起始点开始逐层遍历所有的相邻节点。而在多源
BFS 中我们可以同时从多个源点开始从这些源点出发逐层向外扩展直到达到目标或者遍历完整个图。 多源 BFS 可以用于解决一些问题例如
多个人同时逃生 在一个迷宫中有多个人同时被困在不同的位置需要找到最短路径逃离迷宫。可以从这些人的位置同时开始 BFS第一个相遇的点就是大家逃生的最短路径。多点到达目标问题 在一些网络传播或者路由问题中多个点需要同时到达某个目标点可以使用多源 BFS 找到最短路径。并行计算 在一些并行计算的场景中多源 BFS 可以用于并行地计算多个点到其他点的最短路径。
多源 BFS 的实现方式与单源 BFS 类似只是需要同时从多个源点开始扩展。通常使用队列来进行层次遍历每一层表示到达目标的步数。
01.矩阵
题目链接https://leetcode.cn/problems/01-matrix/
给定一个由 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 开始层序遍历并且记录遍历的层数。当第一次碰到 1 的时候当前的层数就是这个 1 离 0 的最短距离。这一种方式在遍历的时候标记一下处理过的 1 能够做到只用遍历整个矩阵一次就能得到最终结果。但是这里有一个问题 0 是有很多个的我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢 其实很简单我们可以先把所有的 0 都放在队列中把它们当成一个整体每次把当前队列里面的所有元素向外扩展一次。
代码
class Solution{const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};
public:vectorvectorint updateMatrix(vectorvectorint mat) {int mmat.size(),nmat[0].size();vectorvectorint dist(m,vectorint(n,-1));queuepairint,int q;for(int i0;im;i)for(int j0;jn;j)if(mat[i][j]0){q.push({i,j});dist[i][j]0;}while(!q.empty()){auto [a,b]q.front();q.pop();for(int i0;i4;i){int xadx[i],ybdy[i];if(x0xmy0yndist[x][y]-1){dist[x][y]dist[a][b]1;q.push({x,y});}}} return dist;}
};02.飞地的数量
题目链接https://leetcode.cn/problems/number-of-enclaves/
给你一个大小为 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
中间的1要达到边界首先就是要有1在边界并且能够接触到所以我们可以直接在周围一圈做单源BFS遍历1将它改为0再遍历整个数组剩下的1就是出不去的。
代码1
class Solution {const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};int m,n;queuepairint,int q;void bfs(vectorvectorint grid,int i,int j){q.push({i,j});grid[i][j]0;while(!q.empty()){int szq.size();while(sz--){auto [a,b]q.front();q.pop();for(int k0;k4;k){int xadx[k],ybdy[k];if(x0xmy0yngrid[x][y]1){grid[x][y]0;q.push({x,y});}}}}}
public:int numEnclaves(vectorvectorint grid) {mgrid.size(),ngrid[0].size();for(int i0;im;i){if(grid[i][0]1) bfs(grid,i,0);if(grid[i][n-1]1) bfs(grid,i,n-1);}for(int i1;in-1;i){if(grid[0][i]1) bfs(grid,0,i);if(grid[m-1][i]1) bfs(grid,m-1,i);}int ret0;for(int i0;im;i)for(int j0;jn;j)if(grid[i][j]1) ret1;return ret;}
};思路2
使用多源BFS同时对周边的1进行遍历
代码2
class Solution {// 定义四个方向的坐标变化const int dx[4] {0, 0, 1, -1};const int dy[4] {1, -1, 0, 0};public:int numEnclaves(vectorvectorint grid) {int m grid.size(), n grid[0].size();// 用于标记是否访问过的二维布尔型数组vectorvectorbool vis(m, vectorbool(n));// 广度优先搜索的队列queuepairint, int q;// 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)if (grid[i][j] 1) {q.push({i, j});vis[i][j] true;}// 2. 多源 BFSwhile (!q.empty()) {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 grid[x][y] 1 !vis[x][y]) {vis[x][y] true;q.push({x, y});}}}// 3. 统计结果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])ret;return ret;}
};03.地图中的最高点
题目链接https://leetcode.cn/problems/map-of-highest-peak/
给你一个大小为 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 {const int dx[4] {0, 0, 1, -1};const int dy[4] {-1, 1, 0, 0};public:vectorvectorint highestPeak(vectorvectorint isWater) {int m isWater.size(), n isWater[0].size();vectorvectorint dist(m, vectorint(n, -1));queuepairint, int q;for (int i 0; i m; i)for (int j 0; j n; j)if (isWater[i][j]) {dist[i][j] 0;q.push({i, j});}while (!q.empty()) {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;}
};创建一个二维矩阵dist用于存储每个位置到水域的最近距离。初始化所有元素为-1。创建一个队列q用于进行广度优先搜索。将所有水域的位置isWater[i][j]为1的位置加入队列并将其到水域的距离设为0。使用BFS遍历队列不断扩展到达的位置。对于每个位置检查其四个相邻的位置如果相邻位置合法且未被访问过更新其到水域的距离并将该位置加入队列。最终返回计算得到的dist矩阵。
04.地图分析
题目链接https://leetcode.cn/problems/as-far-from-land-as-possible/
你现在手里有一份大小为 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 {const int dx[4]{0,0,1,-1};const int dy[4]{-1,1,0,0};
public:int maxDistance(vectorvectorint grid) {int mgrid.size(),ngrid[0].size();vectorvectorint dist(m,vectorint(n,-1)); queuepairint,int q;for(int i0;im;i)for(int j0;jn;j)if(grid[i][j]){dist[i][j]0;q.push({i,j});}int ret-1;while(!q.empty()){auto [a,b] q.front();q.pop();for(int i0;i4;i){int xadx[i],ybdy[i];if(x0xmy0yndist[x][y]-1){dist[x][y]dist[a][b]1;q.push({x,y});retmax(ret,dist[x][y]);}}}return ret;}
};
