📝前言说明：

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

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

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

点击链接	开始学习
双指针(1)	双指针(2)
双指针(3)	双指针(4)
滑动窗口(1)	滑动窗口(2)
滑动窗口(3)	滑动窗口(4)
二分查找(1)	二分查找(2)
前缀和(1)	前缀和(2)
前缀和(3)	位运算(1)
位运算(2)	模拟算法
快速排序	归并排序
链表	哈希表
字符串	栈
队列 + 宽搜	优先级队列
BFS 解决 FloodFill	BFS 解决最短路径
多源 BFS	BFS 解决拓扑排序

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

---

导论——多源 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)$

---

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