目录
一、542. 01 矩阵 - 力扣（LeetCode）
算法代码：
代码逻辑思路
数据结构初始化
步骤一：队列初始化
步骤二：广度优先搜索
返回结果
关键点总结
广度优先搜索（BFS）
访问标记
复杂度分析
二、1020. 飞地的数量 - 力扣（LeetCode）
算法代码：
代码逻辑思路
数据结构初始化
步骤一：将边界上的陆地单元格加入队列
步骤二：多源 BFS 扩展
步骤三：统计被水包围的陆地单元格数量
关键点总结
多源 BFS
访问标记
复杂度分析
三、1765. 地图中的最高点 - 力扣（LeetCode）
算法代码：
代码逻辑思路
关键点总结
四、1162. 地图分析 - 力扣（LeetCode）
算法代码：
代码逻辑思路
关键点总结
一、542. 01 矩阵 - 力扣（LeetCode）
算法代码：
class Solution {
int dx[4] = {0, 0, 1, -1}; // 四个方向的 x 偏移量
int dy[4] = {1, -1, 0, 0}; // 四个方向的 y 偏移量
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)); // 初始化距离矩阵为 -1
queue<pair<int, int>> q; // BFS 队列
// 1. 把所有的源点加入到队列中
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (mat[i][j] == 0) { // 找到 0 的位置
q.push({i, j}); // 入队
dist[i][j] = 0; // 距离为 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; // 返回结果矩阵
}
};
代码逻辑思路
-
数据结构初始化
-
使用
m和n分别表示矩阵的行数和列数。 -
创建一个
dist矩阵，用于存储每个单元格到最近零的距离，初始化为-1，表示尚未被搜索过。 -
使用一个队列
q来实现广度优先搜索（BFS）。
-
-
步骤一：队列初始化
-
遍历整个矩阵
mat，将所有的0的位置（源点）加入队列q，并将对应的dist值设为0，因为从0到0的距离为0。
-
-
步骤二：广度优先搜索
-
使用 BFS 从所有的
0出发，逐层向外扩展。 -
在每次循环中，取出队列的前一个元素
(a, b)，表示当前正在处理的位置。 -
遍历四个方向（上下左右），计算
(x, y)的新位置。 -
检查新位置是否在矩阵范围内，且
dist[x][y]为-1（表示尚未访问过）：-
如果是，则将
dist[x][y]更新为dist[a][b] + 1，表示新位置到最近0的距离。 -
把新位置
(x, y)加入队列q。
-
-
-
返回结果
-
当队列为空时，所有位置的最短距离都已经计算完毕，返回
dist矩阵。
-
关键点总结
-
广度优先搜索（BFS）
-
BFS 是解决最短路径问题的经典方法，适合用于从多个源点扩展到其它点的场景。
-
通过从所有的
0开始，同时向外扩展，确保每个位置的最短路径都能被正确计算。
-
-
访问标记
-
使用
dist数组来标记每个位置是否已被访问，并存储到最近0的距离。
-
-
复杂度分析
-
时间复杂度为 O(m * n)，因为每个位置最多被访问一次。
-
空间复杂度为 O(m * n)，用于存储
dist矩阵和 BFS 队列。
-
这种方法有效且高效，适用于计算二维矩阵中元素到最近目标元素的距离问题。
二、1020. 飞地的数量 - 力扣（LeetCode）
算法代码：
class Solution {
int dx[4] = {0, 0, 1, -1}; // 四个方向的 x 偏移量
int dy[4] = {1, -1, 0, 0}; // 四个方向的 y 偏移量
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; // BFS 队列
// 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.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; // 返回结果
}
};
代码逻辑思路
-
数据结构初始化
-
使用
m和n分别表示网格的行数和列数。 -
创建一个
vis矩阵，用于记录每个单元格是否被访问过。 -
使用一个队列
q来进行 BFS。
-
-
步骤一：将边界上的陆地单元格加入队列
-
遍历整个网格
grid，在边界（第一行、最后一行、第一列、最后一列）中寻找值为1的单元格。 -
如果找到这样的单元格，将它加入队列
q，并标记为已访问。
-
-
步骤二：多源 BFS 扩展
-
使用 BFS 从队列中的所有陆地单元格开始，逐层向外扩展。
-
在每次循环中，取出队列的前一个元素
(a, b)，表示当前正在处理的位置。 -
遍历四个方向（上下左右），计算新位置
(x, y)。 -
检查新位置是否在矩阵范围内，且值为
1，并且未被访问：-
如果满足条件，标记该位置为已访问，并将其加入队列
q。
-
-
-
步骤三：统计被水包围的陆地单元格数量
-
遍历整个网格
grid，统计值为1并且未被访问的单元格的数量，表示这些单元格是被水包围的陆地单元格。 -
返回这个计数作为结果。
-
关键点总结
-
多源 BFS
-
从所有边界的陆地单元格开始，同时向内扩展，确保能够覆盖所有与边界相连的陆地。
-
BFS 确保每个陆地单元格仅被访问一次。
-
-
访问标记
-
使用
vis数组来标记每个单元格是否已被访问，避免重复计算。
-
-
复杂度分析
-
时间复杂度为 O(m * n)，因为每个单元格最多被访问一次。
-
空间复杂度为 O(m * n)，用于存储访问标记和 BFS 队列。
-
这种方法有效且高效，适用于计算被水包围的陆地单元格的数量。
三、1765. 地图中的最高点 - 力扣（LeetCode）
算法代码：
class Solution {
int dx[4] = {0, 0, 1, -1}; // 四个方向的 x 偏移量
int dy[4] = {1, -1, 0, 0}; // 四个方向的 y 偏移量
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)); // 初始化高度矩阵为 -1
queue<pair<int, int>> q; // BFS 队列
// 1. 把所有的源点加入到队列里面
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (isWater[i][j]) { // 找到水域单元格
dist[i][j] = 0; // 高度设为 0
q.push({i, j}); // 入队
}
// 2. 多源 BFS 扩展
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; // 返回结果矩阵
}
};
代码逻辑思路
-
数据结构初始化
-
使用
m和n分别表示矩阵的行数和列数。 -
创建一个
dist矩阵，用于存储每个单元格的高度，初始值为-1，表示尚未计算。 -
使用一个队列
q来实现 BFS。
-
-
步骤一：将所有水域单元格加入队列
-
遍历整个矩阵
isWater，找到所有值为1的单元格（水域）。 -
将这些水域单元格的对应位置在
dist矩阵中设置为0，并将其加入队列q。
-
-
步骤二：多源 BFS 扩展
-
使用 BFS 从队列中的所有水域单元格开始，逐层向外扩展。
-
在每次循环中，取出队列的前一个元素
(a, b)，表示当前正在处理的位置。 -
遍历四个方向（上下左右），计算新位置
(x, y)。 -
检查新位置是否在矩阵范围内，且
dist[x][y]为-1（表示尚未计算）：-
如果满足条件，则更新
dist[x][y]为dist[a][b] + 1，表示新位置到最近水域的距离。 -
将新位置
(x, y)加入队列q。
-
-
-
返回结果
-
当队列为空时，所有位置的高度都已经计算完毕，返回
dist矩阵。
-
关键点总结
-
多源 BFS
-
BFS 从所有水域单元格同时开始，同时向内扩展，确保所有陆地单元格的高度能够被正确计算。
-
BFS 能够保证每个陆地单元格的高度是距离最近水域单元格的最短距离。
-
-
访问标记
-
使用
dist数组来标记每个单元格的高度，并避免重复计算。
-
-
复杂度分析
-
时间复杂度为 O(m * n)，每个单元格最多被访问一次。
-
空间复杂度为 O(m * n)，用于存储高度矩阵和 BFS 队列。
-
这种方法有效且高效，适用于计算二维矩阵中每个单元格的高度，特别是在有障碍物（如水域）时。
四、1162. 地图分析 - 力扣（LeetCode）
算法代码：
class Solution {
int dx[4] = {0, 0, 1, -1}; // 四个方向的 x 偏移量
int dy[4] = {1, -1, 0, 0}; // 四个方向的 y 偏移量
public:
int maxDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, -1)); // 初始化距离矩阵为 -1
queue<pair<int, int>> q; // BFS 队列
// 1. 把所有陆地单元格加入到队列里面
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j]) { // 判断是否为陆地
dist[i][j] = 0; // 陆地的距离为 0
q.push({i, j}); // 入队
}
int ret = -1; // 最大距离初始化为 -1
// 2. 多源 BFS 扩展
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; // 返回最大距离
}
};
代码逻辑思路
-
数据结构初始化
-
使用
m和n分别表示网格的行数和列数。 -
创建一个
dist矩阵，用于存储每个单元格的距离，初始值为-1，表示尚未计算。 -
使用一个队列
q来实现 BFS。
-
-
步骤一：将所有陆地单元格加入队列
-
遍历整个网格
grid，找到所有值为1的单元格（陆地）。 -
将这些陆地单元格的对应位置在
dist矩阵中设置为0，并将它们加入队列q。
-
-
步骤二：多源 BFS 扩展
-
使用 BFS 从队列中的所有陆地单元格开始，逐层向外扩展。
-
在每次循环中，取出队列的前一个元素
(a, b)，表示当前正在处理的位置。 -
遍历四个方向（上下左右），计算新位置
(x, y)。 -
检查新位置是否在矩阵范围内，且
dist[x][y]为-1（表示尚未计算）：-
如果满足条件，则更新
dist[x][y]为dist[a][b] + 1，表示新位置到最近水域的距离。 -
将新位置
(x, y)加入队列q。 -
在更新后，更新
ret为当前最大距离。
-
-
-
返回结果
-
当队列为空时，所有位置的最大距离都已经计算完毕，返回
ret。
-
关键点总结
-
多源 BFS
-
从所有陆地单元格同时开始，BFS 确保所有水域单元格的最大距离能够被正确计算。
-
BFS 的逐层扩展特性确保了每个单元格到最近水域单元格的距离是最短的。
-
-
访问标记
-
使用
dist数组来标记每个单元格的距离，并避免重复计算。
-
-
复杂度分析
-
时间复杂度为 O(m * n)，每个单元格最多被访问一次。
-
空间复杂度为 O(m * n)，用于存储距离矩阵和 BFS 队列。
-
这种方法有效且高效，适用于计算二维矩阵中每个陆地单元格到最近水域单元格的最大距离。
