【专题十七】多源 BFS

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

题单汇总链接：点击 → 题单汇总（暂时未整理，因为还没刷完）

导论——多源 BFS

多元最短路问题：起始点有多个，去同一个终点

• 前提：BFS解决的最短路问题都是边权为 1 的
• 解法一：把多源最短路问题转换成若干个单源最短路问题——暴力枚举每个起点，对每个起点进行单源最短路问题分析【但是时间复杂度高：超时】
• 解法二：把所有的源点当成一个“超级源点”——从“超级源点”出发，一次单源最短路问题
  • 如何求：“超级源点” ？
  • 把所有的起始节点加入到队列中，即：第一层由单源的一个节点变成了多源的多个节点（只不过这些节点都属于第一层罢了）
  • 多个源点可能开辟出不同的路，在不同的路中：后到达的节点会被hash淘汰

542. 01 矩阵

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

优质解

思路：

• 解法一：把 1 当成起点的话，要遍历整个矩阵
• 解法二：把 0 当起点：从所有 0 走到某一个 1 的最短距离 == 从 1 走到最近 0 的距离

代码：

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        int m = mat.size(), n = mat[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> dis(m, vector<int>(n, -1));
        // 先获得"超级源点"
        for(int i = 0 ; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(mat[i][j] == 0)
                {
                    q.push({i, j});
                    dis[i][j] = 0;
                }
            }
        }
        
        // 从"超级源点"开始扩展
        while(q.size())
        {
            // int sz = q.size(); 为什么可以不计算 sz ？
            // 因为之前的 sz 是和 step 配合使用的，我们通过sz知道是在哪一层
            // 但是现在，下一个dis中填写的内容可以根据上一个dis中的内容决定
            // 并且，一定是上一层的节点pop出去以后，才会处理上一层加入的后续节点
            auto [a, b] = q.front();
            q.pop();
            for(int j = 0; j < 4; j++)
            {
                int x = a + dx[j], y = b + dy[j];
                if(x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1)
                {
                    dis[x][y] = dis[a][b] + 1;
                    q.push({x, y}); 
                }
            }
        }
        return dis;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

1020. 飞地的数量

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

个人解

屎山代码：

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) 
    {
        // 这就是 floodfill
        // 只不过从边缘 1 开始先标记连通块的时候可以使用 多源 bfs 标记

        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        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])
                {
                    grid[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])
                {
                    grid[x][y] = 0;
                    q.push({x, y});
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j])
                    ans++;
            }
        }
        return ans;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

1765. 地图中的最高点

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

个人解

思路：

• 和 01 矩阵一样

屎山代码：

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) 
    {
        // 自行安排出最高高度
        // 以水域为起点，能到达的最远的陆地最高(走最短路径)
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> high(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])
                {
                    q.push({i, j});
                    high[i][j] = 0;
                }
            }
        }
        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 && high[x][y] == -1)
                {
                    high[x][y] = high[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return high;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

1162. 地图分析

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

个人解

思路：

// 海洋到最近的陆地的距离 == 陆地到海洋的最短路径
// 以陆地为起始点做 bfs

用时：14:00
屎山代码：

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) 
    {
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(grid[i][j])
                    q.push({i, j});
            }
        }
        int ans = 0;
        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])
                {
                    grid[x][y] = grid[a][b] + 1;
                    ans = max(ans, grid[x][y]);
                    q.push({x, y});
                }
            }
        }
        return ans - 1; // 因为第一次是 1 -> 2，但其实是 1
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！