BFS算法篇——从晨曦到星辰，BFS算法在多源最短路径问题中的诗意航行（下）

用户11379153

发布于 2025-11-05 16:28:19

1060

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

引言

上篇我们介绍了多源BFS的相关背景知识，本篇我们将结合具体题目分析，进一步深化对于BFS算法的理解运用。

一、01矩阵

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

1.2 题目分析：

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

1.3 思路讲解：

返回的矩阵中，原来为0的节点，保持为0即可，而原来为1的节点，则指应修改为到最近的0的距离

根据上篇了解的多源bfs的基础知识，我们在本题中有多个起点，即矩阵中原来为1的节点
与bfs求取最短路径相同，我们需要将起点入队列，但是此处可以采取正难则反的思想，把0当作起点，求取最近的1

这是由于我们把1当作起点进行遍历时，需要统计存储多条路径，在进行比较时较为繁琐

由于要返回同等规模的矩阵dis，我们可以在将起点入队列时，同步将dis中相应的节点初始化为0，-1则表示尚未找到最短路径的起点
之后采取上下左右层序遍历的方式，记录各源点所对应的最短距离

1.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size(),n=mat[0].size();
        //全部初始化为-1，表示尚未计算出最短路径
        vector<vector<int>> dis(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)
                {
                    dis[i][j]=0;
                    q.push({i,j});
                }
            }
        }
        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 && dis[x][y]==-1)
                {
                    q.push({x,y});
                    dis[x][y]=dis[a][b]+1;//步数加1
                }

            }

        }
        return dis;
        
    }
};

二、飞地的数量

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

2.2 题目分析：

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
返回其中被0包围的连续1的数量（可以理解为一些相邻的1组成岛屿，被海洋包围）
边界上的1不能算作岛屿

2.3 思路讲解：

乍一看会感觉无从下手，找不出与多源bfs算法的关系，但如果同样采取正难则反的思想，就迎刃而解了：

我们把1当作起点，进行多源bfs的遍历，如果在上下左右四个方向的遍历过程中，找到了1，则说明这是一块与边界1相邻的陆地，无法形成岛屿
在全部遍历完成后，原数组内为1且对应标记数组为false的节点，则为一块岛屿

2.4 代码实现：

class Solution {
public:
    int dx[4] = { 0,0,-1,1 };
    int dy[4] = { 1,-1,0,0 };
    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入队列
        for (int i = 0; i < m; i++)
        {
            if (grid[i][0] == 1)
            {
                q.push({ i,0 });
                vis[i][0] = true;
            }
            if (grid[i][n - 1] == 1)
            {
                q.push({ i,n - 1 });
                vis[i][n - 1] = true;
            }
        }
        for (int j = 0; j < n; j++)
        {
            if (grid[0][j] == 1)
            {
                q.push({ 0,j });
                vis[0][j] = true;
            }
            if (grid[m - 1][j] == 1)
            {
                q.push({ m - 1,j });
                vis[m - 1][j] = true;
            }
        }
        //多源bfs
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            vis[a][b] = true;
            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])
                {
                    q.push({ x,y });
                    vis[x][y] = true;
                }
            }
        }
        //统计结果
        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] == false)
                {
                    ret++;
                }
            }
        }
        return ret;
    }
};

三、地图中的最高点

3.1 题目链接：https://leetcode.cn/problems/map-of-highest-peak/description/

3.2 题目分析：

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。如果 isWater[i][j] == 1 ，格子(i, j) 是一个 水域 格子。

水域的高度必须为0，相邻的格子之间高度差最大为1
要求返回一共m x n的矩阵，使得矩阵中的最高高度值最大

3.3 思路讲解：

本题与01矩阵类似，我们只需要把遍历矩阵，将所有水域入队列，之后在bfs遍历过程中，将相邻的陆地高度更新为dis[x][y]=dis[a][b]+1即可

3.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m=isWater.size(),n=isWater[0].size();
        
        vector<vector<int>> dis(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]==1)
                {
                    q.push({i,j});
                    
                    dis[i][j]=0;//水域的高度为0
                }
            }
        }
        while(q.size())
        {
            int sz=q.size();
            while(sz--)
            {
                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 && !isWater[x][y] && dis[x][y]==-1)//条件为不越界并且为陆地且为被遍历过
                    {
                        q.push({x,y});
                        dis[x][y]=dis[a][b]+1;
                    }

                }
            }

        }
        return dis;

    
        
    }
};

四、地图分析

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

4.2 题目分析：

有一份大小为 n x n 的网格 grid，上面的每个单元格都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

4.3 思路讲解：

与上题思路基本相同，采取同样策略，将海洋入队列层序遍历即可
注意距离的计算方式

4.4 代码实现：

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    int ret=-1;//最大高度
    int maxDistance(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        vector<vector<int>> dis(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]==1)
                {
                    dis[i][j]=0;
                    q.push({i,j});

                }
            }
        }
        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 && grid[x][y]==0 && dis[x][y]==-1)
                    {
                        q.push({x,y});
                        dis[x][y]=dis[a][b]+1;
                        ret=max(ret,dis[x][y]);//更新高度
                    }
                }
            

        }
        return ret;

        
    }
};