刷题训练之多源 BFS

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握多源 BFS算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

采用多源BFS算法

🌙topic-->1

题目链接：1. - 力扣（LeetCode）

题目分析：

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

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

算法原理：

解法：多源 BFS

图解：

代码演示：

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};public:vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int m = mat.size(), n = mat[0].size();// dist[i][j] == -1 表⽰：没有搜索过// dist[i][j] != -1 表⽰：最短距离vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;// 1. 把所有的源点加⼊到队列中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;}// 2. ⼀层⼀层的往外扩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 && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.push({x, y});}}}return dist;}
};

🌙topic-->2

题目链接：2. - 力扣（LeetCode）

题目分析：

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

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

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

算法原理：

解法：多源 BFS

图解：

代码演示：

class Solution {int dx[4] = {0, 0, 1, -1};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. 多源 bfswhile (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] == 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;}
};

🌙topic-->3

题目链接：2. - 力扣（LeetCode）

题目分析：

给你一个大小为 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) 的高度。如果有多种解法，请返回 任意一个 。

算法原理：

解法：多源 BFS

图解：

01矩阵的变型题，直接⽤多源 bfs 解决即可。

代码演示：

class Solution {int dx[4] = {0, 0, 1, -1};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;// 1. 把所有的源点加⼊到队列⾥⾯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});}// 2. 多源 bfswhile (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 && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.push({x, y});}}}return dist;}
};

🌙topic-->4

题目链接：4. - 力扣（LeetCode）

题目分析：

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

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

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

算法原理：

解法：多源 BFS

图解：

01矩阵的变型题，直接⽤多源 bfs 解决即可。

代码演示：

class Solution {int dx[4] = {0, 0, 1, -1};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.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 && dist[x][y] == -1) {dist[x][y] = dist[a][b] + 1;q.push({x, y});ret = max(ret, dist[x][y]);}}}return ret;}
};