算法沉淀——多源 BFS(leetcode真题剖析)

这篇具有很好参考价值的文章主要介绍了算法沉淀——多源 BFS(leetcode真题剖析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode


多源 BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的 BFS 中,我们通常从一个起始点开始,逐层遍历所有的相邻节点。而在多源 BFS 中,我们可以同时从多个源点开始,从这些源点出发,逐层向外扩展,直到达到目标或者遍历完整个图。

多源 BFS 可以用于解决一些问题,例如:

  1. 多个人同时逃生: 在一个迷宫中,有多个人同时被困在不同的位置,需要找到最短路径逃离迷宫。可以从这些人的位置同时开始 BFS,第一个相遇的点就是大家逃生的最短路径。
  2. 多点到达目标问题: 在一些网络传播或者路由问题中,多个点需要同时到达某个目标点,可以使用多源 BFS 找到最短路径。
  3. 并行计算: 在一些并行计算的场景中,多源 BFS 可以用于并行地计算多个点到其他点的最短路径。

多源 BFS 的实现方式与单源 BFS 类似,只是需要同时从多个源点开始扩展。通常使用队列来进行层次遍历,每一层表示到达目标的步数。

01.矩阵

题目链接:https://leetcode.cn/problems/01-matrix/

给定一个由 01 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1

示例 1:
算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode

输入:mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]

示例 2:
算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode

输入:mat = [[0,0,0],[0,1,0],[1,1,1]]
输出:[[0,0,0],[0,1,0],[1,2,1]]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

思路

从 0 开始层序遍历,并且记录遍历的层数。当第一次碰到 1 的时候,当前的层数就是这个 1 离 0 的最短距离。这一种方式,在遍历的时候标记一下处理过的 1 ,能够做到只用遍历整个矩阵一次,就能得到最终结果。但是,这里有一个问题, 0 是有很多个的,我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢? 其实很简单,我们可以先把所有的 0 都放在队列中,把它们当成一个整体,每次把当前队列里面的所有元素向外扩展一次。

代码文章来源地址https://www.toymoban.com/news/detail-827425.html

class Solution{
    const int dx[4]={0,0,1,-1};
    const int dy[4]={-1,1,0,0};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n,-1));
        queue<pair<int,int>> q;

        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.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;
    }
};

02.飞地的数量

题目链接:https://leetcode.cn/problems/number-of-enclaves/

给你一个大小为 m x n 的二进制矩阵 grid ,其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻(上、下、左、右)的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1:
算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode

输入:grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出:3
解释:有三个 1 被 0 包围。一个 1 没有被包围,因为它在边界上。

示例 2:
算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode

输入:grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出:0
解释:所有 1 都在边界上或可以到达边界。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] 的值为 01

思路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;
    queue<pair<int,int>> q;

    void bfs(vector<vector<int>>& grid,int i,int j){
        q.push({i,j});
        grid[i][j]=0;

        while(!q.empty()){
            int sz=q.size();
            while(sz--){
                auto [a,b]=q.front();
                q.pop();

                for(int k=0;k<4;++k){
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
                        grid[x][y]=0;
                        q.push({x,y});
                    }
                }
            }
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        for(int i=0;i<m;++i){
            if(grid[i][0]==1) bfs(grid,i,0);
            if(grid[i][n-1]==1) bfs(grid,i,n-1);
        }
        for(int i=1;i<n-1;++i){
            if(grid[0][i]==1) bfs(grid,0,i);
            if(grid[m-1][i]==1) bfs(grid,m-1,i);
        }

        int ret=0;
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(grid[i][j]==1) ret+=1;

        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(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 用于标记是否访问过的二维布尔型数组
        vector<vector<bool>> vis(m, vector<bool>(n));
        // 广度优先搜索的队列
        queue<pair<int, 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. 多源 BFS
        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 && 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:

**算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode
**

输入:isWater = [[0,1],[0,0]]
输出:[[1,0],[2,1]]
解释:上图展示了给各个格子安排的高度。
蓝色格子是水域格,绿色格子是陆地格。

示例 2:

**算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode
**

输入: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:
    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));
        queue<pair<int, 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;
    }
};
  1. 创建一个二维矩阵dist,用于存储每个位置到水域的最近距离。初始化所有元素为-1。
  2. 创建一个队列q,用于进行广度优先搜索。将所有水域的位置(isWater[i][j]为1的位置)加入队列,并将其到水域的距离设为0。
  3. 使用BFS遍历队列,不断扩展到达的位置。对于每个位置,检查其四个相邻的位置,如果相邻位置合法且未被访问过,更新其到水域的距离并将该位置加入队列。
  4. 最终,返回计算得到的dist矩阵。

04.地图分析

题目链接:https://leetcode.cn/problems/as-far-from-land-as-possible/

你现在手里有一份大小为 n x n 的 网格 grid,上面的每个 单元格 都用 01 标记好了。其中 0 代表海洋,1 代表陆地。

请你找出一个海洋单元格,这个海洋单元格到离它最近的陆地单元格的距离是最大的,并返回该距离。如果网格上只有陆地或者海洋,请返回 -1

我们这里说的距离是「曼哈顿距离」( Manhattan Distance):(x0, y0)(x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1|

示例 1:

**算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode
**

输入:grid = [[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释: 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大,最大距离为 2。

示例 2:

**算法沉淀——多源 BFS(leetcode真题剖析),算法沉淀,算法,宽度优先,leetcode
**

输入:grid = [[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释: 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大,最大距离为 4。

提示:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[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(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dist(m,vector<int>(n,-1)); 
        queue<pair<int,int>> q;

        for(int i=0;i<m;++i)
            for(int j=0;j<n;++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 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;
    }
};

到了这里,关于算法沉淀——多源 BFS(leetcode真题剖析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法沉淀——递归(leetcode真题剖析)

    递归是一种通过调用自身的方式来解决问题的算法。在递归算法中,问题被分解为更小的相似子问题,然后通过对这些子问题的解进行组合来解决原始问题。递归算法通常包含两个主要部分: 基本情况(Base Case): 定义问题的最小规模,直接解答而不再进行递归。基本情况

    2024年02月20日
    浏览(42)
  • 算法沉淀——栈(leetcode真题剖析)

    栈(Stack)是一种基于先进后出(Last In, First Out,LIFO)原则的数据结构。栈具有两个主要的操作: 压栈(Push) :将元素添加到栈的顶部。 出栈(Pop) :从栈的顶部移除元素。 栈常常用于需要反转操作顺序的场景,或者在需要记录操作历史的情况下。在算法中,栈的应用广

    2024年02月20日
    浏览(38)
  • 算法沉淀——贪心算法一(leetcode真题剖析)

    贪心算法(Greedy Algorithm)是一种基于贪心策略的优化算法,它通常用于求解最优化问题,每一步都选择当前状态下的最优解,以期望通过局部最优的选择最终达到全局最优。贪心算法的思想是在每一步都做出在当前状态下局部最优的选择,而不考虑未来可能造成的影响。 在

    2024年03月08日
    浏览(48)
  • 算法沉淀——贪心算法六(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/broken-calculator/ 在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作: **双倍(Double):**将显示屏上的数字乘 2; **递减(Decrement):**将显示屏上的数字减 1 。 给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操

    2024年04月11日
    浏览(43)
  • 算法沉淀——贪心算法五(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/jump-game-ii/ 给定一个长度为 n 的 0 索引 整数数组 nums 。初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处: 0 = j = nums[i] i + j n 返回到达 nums[n - 1] 的最小跳跃次

    2024年04月11日
    浏览(48)
  • 算法沉淀——贪心算法三(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/ 给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。 在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。 返回 你能获得

    2024年03月24日
    浏览(38)
  • 算法沉淀——贪心算法二(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如, [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 示

    2024年03月19日
    浏览(50)
  • 算法沉淀——贪心算法七(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/integer-replacement/ 给定一个正整数 n ,你可以做如下操作: 如果 n 是偶数,则用 n / 2 替换 n 。 如果 n 是奇数,则可以用 n + 1 或 n - 1 替换 n 。 返回 n 变为 1 所需的 最小替换次数 。 示例 1: 示例 2: 示例 3: 提示: 1 = n = 2^31 - 1 思路 这里我们

    2024年03月23日
    浏览(47)
  • 算法沉淀——穷举、暴搜、深搜、回溯、剪枝综合练习一(leetcode真题剖析)

    题目链接:https://leetcode.cn/problems/permutations/ 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1: 示例 2: 示例 3: 提示: 1 = nums.length = 6 -10 = nums[i] = 10 nums 中的所有整数 互不相同 思路 这是一个典型的回溯问题,需要在每

    2024年02月21日
    浏览(61)
  • 算法:BFS宽度优先遍历

    本篇总结的是BFS算法,BFS算法相比起DFS算法来说还是比较简单的 这里提供一种双端队列的做法,也可以在合适的层数逆序

    2024年02月21日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包