算法沉淀——多源 BFS（leetcode真题剖析）

算法沉淀——多源 BFS（leetcode真题剖析）

• 01.矩阵
• 02.飞地的数量
• 03.地图中的最高点
• 04.地图分析

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

多源 BFS 可以用于解决一些问题，例如：

1. 多个人同时逃生： 在一个迷宫中，有多个人同时被困在不同的位置，需要找到最短路径逃离迷宫。可以从这些人的位置同时开始 BFS，第一个相遇的点就是大家逃生的最短路径。
2. 多点到达目标问题： 在一些网络传播或者路由问题中，多个点需要同时到达某个目标点，可以使用多源 BFS 找到最短路径。
3. 并行计算： 在一些并行计算的场景中，多源 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.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 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。

代码

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：

输入：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.length
• n == grid[i].length
• 1 <= m, n <= 500
• grid[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;
    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：

**
**

输入：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:
    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，上面的每个 单元格 都用 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.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;
    }
};