主页 > 互联网 >

FloodFill算法（典型算法思想）——OJ例题算法解析思路

互联网
2025-09-20 01:21:01

一、733. 图像渲染 - 力扣（LeetCode）

算法代码：

代码思路

问题描述

算法选择

代码结构

代码详解

1. 成员变量

2. floodFill 函数

参数：

逻辑：

3. dfs 函数

参数：

逻辑：

代码优化

边界检查优化

使用 BFS

空间优化

示例运行

总结

二、200. 岛屿数量 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

遍历网格

DFS 函数

3. 代码实现细节

方向数组

边界检查

访问标记

4. 优化建议

空间优化

广度优先搜索（BFS）

5. 复杂度分析

6. 总结

三、695. 岛屿的最大面积 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

遍历网格

DFS 函数

3. 代码实现细节

方向数组

边界检查

访问标记

4. 优化建议

空间优化

广度优先搜索（BFS）

5. 复杂度分析

6. 总结

四、130. 被围绕的区域 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

步骤 1：标记边界及其相连的 'O'

步骤 2：还原网格

DFS 函数

3. 代码实现细节

边界遍历

DFS 的终止条件

临时标记

4. 优化建议

空间优化

广度优先搜索（BFS）

5. 复杂度分析

6. 总结

五、417. 太平洋大西洋水流问题 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

步骤 1：标记能够流入太平洋的位置

步骤 2：标记能够流入大西洋的位置

步骤 3：找到同时能够流入太平洋和大西洋的位置

DFS 函数

3. 代码实现细节

边界遍历

DFS 的终止条件

结果集

4. 优化建议

空间优化

广度优先搜索（BFS）

5. 复杂度分析

6. 总结

六、529. 扫雷游戏 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

点击逻辑

DFS 函数

3. 代码实现细节

边界检查

递归终止条件

地雷数量统计

4. 优化建议

广度优先搜索（BFS）

空间优化

5. 复杂度分析

6. 总结

七、LCR 130. 衣橱整理 - 力扣（LeetCode）

算法代码：

1. 问题描述

2. 代码思路

初始化

DFS 函数

检查函数

3. 代码实现细节

边界检查

数位之和计算

访问标记

4. 优化建议

广度优先搜索（BFS）

空间优化

5. 复杂度分析

6. 总结

一、733. 图像渲染 - 力扣（LeetCode）

算法代码： class Solution { int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int m, n; int prev; public: vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { if (image[sr][sc] == color) return image; m = image.size(), n = image[0].size(); prev = image[sr][sc]; dfs(image, sr, sc, color); return image; } void dfs(vector<vector<int>>& image, int i, int j, int color) { image[i][j] = color; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) { dfs(image, x, y, color); } } } };

这段代码实现了一个经典的 Flood Fill（泛洪填充）算法，用于将图像中的某个区域填充为指定颜色。以下是代码的详细思路和解释：

代码思路

问题描述给定一个二维矩阵 image，表示一张图像，其中每个元素代表一个像素的颜色值。从指定的起始位置 (sr, sc) 开始，将与起始位置颜色相同的所有连通区域填充为新的颜色 color。算法选择使用深度优先搜索（DFS）来遍历所有与起始位置颜色相同的像素，并将其修改为新的颜色。代码结构 floodFill 函数是入口函数，负责初始化并调用 DFS。dfs 函数是递归函数，负责遍历并修改像素颜色。

代码详解 1. 成员变量 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; dx 和 dy 是方向数组，用于表示上下左右四个方向的移动。 int m, n; m 和 n 分别表示图像的行数和列数。 int prev; prev 保存起始位置 (sr, sc) 的原始颜色，用于判断哪些像素需要被填充。

2. floodFill 函数 vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) { if (image[sr][sc] == color) return image; m = image.size(), n = image[0].size(); prev = image[sr][sc]; dfs(image, sr, sc, color); return image; } 参数： image：输入的图像矩阵。sr 和 sc：起始位置的行和列。color：要填充的新颜色。逻辑：如果起始位置的颜色已经是目标颜色 color，直接返回原图像（无需修改）。否则，初始化 m、n 和 prev，然后调用 dfs 函数开始填充。返回修改后的图像。

3. dfs 函数 void dfs(vector<vector<int>>& image, int i, int j, int color) { image[i][j] = color; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) { dfs(image, x, y, color); } } } 参数： image：输入的图像矩阵。i 和 j：当前像素的位置。color：要填充的新颜色。逻辑：将当前像素 (i, j) 的颜色修改为 color。遍历上下左右四个方向：如果相邻像素 (x, y) 在图像范围内，并且颜色等于 prev，则递归调用 dfs 继续填充。

代码优化边界检查优化在 dfs 中，边界检查可以提前到递归调用之前，避免不必要的递归。使用 BFS 如果图像较大，递归可能导致栈溢出。可以使用广度优先搜索（BFS）替代 DFS，避免递归深度过大。空间优化如果需要进一步优化空间，可以修改 image 中的颜色值，避免使用额外的标记数组。

示例运行

假设输入如下：

image = [ [1, 1, 1], [1, 1, 0], [1, 0, 1] ] sr = 1, sc = 1, color = 2

运行 floodFill 后，输出为：

[ [2, 2, 2], [2, 2, 0], [2, 0, 1] ]

总结这段代码通过 DFS 实现了 Flood Fill 算法，能够高效地将图像中的连通区域填充为指定颜色。代码逻辑清晰，易于理解，但需要注意递归深度的问题。如果图像较大，建议使用 BFS 或迭代 DFS 来避免栈溢出。

二、200. 岛屿数量 - 力扣（LeetCode）

算法代码： class Solution { vector<vector<bool>> vis; int m, n; public: int numIslands(vector<vector<char>>& grid) { m = grid.size(), n = grid[0].size(); vis = vector<vector<bool>>(m, vector<bool>(n)); int ret = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (!vis[i][j] && grid[i][j] == '1') { ret++; dfs(grid, i, j); } } return ret; } int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; void dfs(vector<vector<char>>& grid, int i, int j) { vis[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') { dfs(grid, x, y); } } } };

这段代码实现了一个经典的“岛屿数量”问题，使用了深度优先搜索（DFS）来遍历二维网格中的岛屿。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个二维网格 grid，其中 '1' 表示陆地，'0' 表示水域。

岛屿是由相邻的陆地组成的，相邻指的是水平或垂直方向的相邻。

要求计算网格中岛屿的数量。

2. 代码思路初始化

vis 是一个二维布尔数组，用于记录每个位置是否已经被访问过。

m 和 n 分别表示网格的行数和列数。

ret 用于记录岛屿的数量。

遍历网格

使用双重循环遍历整个网格。

如果当前位置是陆地（grid[i][j] == '1'）且未被访问过（!vis[i][j]），则说明发现了一个新的岛屿，增加 ret 的计数，并调用 dfs 函数来标记与该陆地相连的所有陆地。

DFS 函数

dfs 函数用于递归地标记与当前陆地相连的所有陆地。

首先将当前位置标记为已访问（vis[i][j] = true）。

然后遍历当前位置的四个相邻方向（上、下、左、右），如果相邻位置是陆地且未被访问过，则递归调用 dfs。

3. 代码实现细节方向数组

dx 和 dy 数组用于表示四个方向的移动。dx 表示行的变化，dy 表示列的变化。

例如，dx[0] = 0, dy[0] = 1 表示向右移动。

边界检查

在 dfs 函数中，检查相邻位置是否在网格范围内（x >= 0 && x < m && y >= 0 && y < n），以避免越界访问。

访问标记

使用 vis 数组来避免重复访问已经处理过的陆地。

4. 优化建议空间优化

可以直接修改 grid 数组，将访问过的陆地标记为 '0'，从而省去 vis 数组的空间开销。

修改后的 dfs 函数可以这样实现：

void dfs(vector<vector<char>>& grid, int i, int j) { grid[i][j] = '0'; // 标记为已访问 for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') { dfs(grid, x, y); } } } 广度优先搜索（BFS）

除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的网格。

5. 复杂度分析

时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数。每个位置最多被访问一次。

空间复杂度：O(m * n)，主要是 vis 数组的空间开销。如果使用原地修改 grid 的方法，空间复杂度可以优化到 O(1)。

6. 总结

这段代码通过 DFS 遍历网格，有效地计算了岛屿的数量。

通过方向数组和边界检查，代码简洁且易于理解。

可以通过优化空间复杂度来进一步提升代码的效率。

三、695. 岛屿的最大面积 - 力扣（LeetCode）

算法代码： class Solution { bool vis[51][51]; int m, n; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int count; public: int maxAreaOfIsland(vector<vector<int>>& grid) { m = grid.size(), n = grid[0].size(); int ret = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (!vis[i][j] && grid[i][j] == 1) { count = 0; dfs(grid, i, j); ret = max(ret, count); } return ret; } void dfs(vector<vector<int>>& grid, int i, int j) { count++; vis[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1) { dfs(grid, x, y); } } } };

这段代码实现了一个经典的“岛屿最大面积”问题，使用了深度优先搜索（DFS）来遍历二维网格中的岛屿，并计算每个岛屿的面积，最终返回最大岛屿的面积。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个二维网格 grid，其中 1 表示陆地，0 表示水域。

岛屿是由相邻的陆地组成的，相邻指的是水平或垂直方向的相邻。

要求计算网格中最大岛屿的面积。

2. 代码思路初始化

vis 是一个二维布尔数组，用于记录每个位置是否已经被访问过。

m 和 n 分别表示网格的行数和列数。

count 用于记录当前岛屿的面积。

ret 用于记录最大岛屿的面积。

遍历网格

使用双重循环遍历整个网格。

如果当前位置是陆地（grid[i][j] == 1）且未被访问过（!vis[i][j]），则说明发现了一个新的岛屿，初始化 count 为 0，并调用 dfs 函数来计算该岛屿的面积。

更新 ret 为当前岛屿面积和 ret 中的较大值。

DFS 函数

dfs 函数用于递归地计算与当前陆地相连的所有陆地的面积。

首先将当前位置标记为已访问（vis[i][j] = true），并增加 count 的计数。

然后遍历当前位置的四个相邻方向（上、下、左、右），如果相邻位置是陆地且未被访问过，则递归调用 dfs。

3. 代码实现细节方向数组

dx 和 dy 数组用于表示四个方向的移动。dx 表示行的变化，dy 表示列的变化。

例如，dx[0] = 0, dy[0] = 1 表示向右移动。

边界检查

在 dfs 函数中，检查相邻位置是否在网格范围内（x >= 0 && x < m && y >= 0 && y < n），以避免越界访问。

访问标记

使用 vis 数组来避免重复访问已经处理过的陆地。

4. 优化建议空间优化

可以直接修改 grid 数组，将访问过的陆地标记为 0，从而省去 vis 数组的空间开销。

修改后的 dfs 函数可以这样实现：

void dfs(vector<vector<int>>& grid, int i, int j) { count++; grid[i][j] = 0; // 标记为已访问 for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) { dfs(grid, x, y); } } } 广度优先搜索（BFS）

除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的网格。

5. 复杂度分析

时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数。每个位置最多被访问一次。

空间复杂度：O(m * n)，主要是 vis 数组的空间开销。如果使用原地修改 grid 的方法，空间复杂度可以优化到 O(1)。

6. 总结

这段代码通过 DFS 遍历网格，有效地计算了每个岛屿的面积，并返回最大岛屿的面积。

通过方向数组和边界检查，代码简洁且易于理解。

可以通过优化空间复杂度来进一步提升代码的效率。

四、130. 被围绕的区域 - 力扣（LeetCode）

算法代码： class Solution { int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; int m, n; public: void solve(vector<vector<char>>& board) { m = board.size(), n = board[0].size(); // 1. 把边界的 O 相连的联通块，全部修改成 . for (int j = 0; j < n; j++) { if (board[0][j] == 'O') dfs(board, 0, j); if (board[m - 1][j] == 'O') dfs(board, m - 1, j); } for (int i = 0; i < m; i++) { if (board[i][0] == 'O') dfs(board, i, 0); if (board[i][n - 1] == 'O') dfs(board, i, n - 1); } // 2. 还原 for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) { if (board[i][j] == '.') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } void dfs(vector<vector<char>>& board, int i, int j) { board[i][j] = '.'; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') { dfs(board, x, y); } } } };

这段代码实现了一个经典的“被围绕的区域”问题，使用了深度优先搜索（DFS）来标记和修改二维网格中的特定区域。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个二维网格 board，其中 'O' 表示空白区域，'X' 表示障碍物。

要求将所有被 'X' 围绕的 'O' 修改为 'X'。

边界上的 'O' 以及与其相连的 'O' 不会被修改。

2. 代码思路初始化

dx 和 dy 数组用于表示四个方向的移动（上、下、左、右）。

m 和 n 分别表示网格的行数和列数。

步骤 1：标记边界及其相连的 'O'

遍历网格的边界（第一行、最后一行、第一列、最后一列）。

如果边界上的点是 'O'，则调用 dfs 函数，将其及其相连的 'O' 修改为 '.'（临时标记）。

这样做的目的是保留所有与边界相连的 'O'，这些 'O' 不会被修改为 'X'。

步骤 2：还原网格

遍历整个网格：

将标记为 '.' 的点还原为 'O'。

将未被标记的 'O' 修改为 'X'（这些 'O' 是被围绕的区域）。

DFS 函数

dfs 函数用于递归地标记与当前 'O' 相连的所有 'O'。

将当前点标记为 '.'。

遍历四个方向，如果相邻点是 'O'，则递归调用 dfs。

3. 代码实现细节边界遍历

分别遍历第一行、最后一行、第一列和最后一列，确保所有边界上的 'O' 都被处理。

DFS 的终止条件

在 dfs 函数中，通过检查坐标是否在网格范围内（x >= 0 && x < m && y >= 0 && y < n）来避免越界访问。

临时标记

使用 '.' 作为临时标记，避免直接修改 'O' 导致后续判断错误。

4. 优化建议空间优化

可以直接修改 board 数组，省去额外的标记数组。

代码已经实现了这一点，通过将边界相连的 'O' 修改为 '.'，最后再还原。

广度优先搜索（BFS）

除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的网格。

5. 复杂度分析

时间复杂度：O(m * n)，其中 m 是网格的行数，n 是网格的列数。每个位置最多被访问一次。

空间复杂度：O(m * n)，主要是递归调用栈的空间开销。如果使用 BFS，空间复杂度可以优化到 O(min(m, n))。

6. 总结

这段代码通过 DFS 遍历网格，有效地标记了与边界相连的 'O'，并将其保留。

通过临时标记和还原操作，代码简洁且易于理解。

可以通过优化空间复杂度或使用 BFS 来进一步提升代码的效率。

五、417. 太平洋大西洋水流问题 - 力扣（LeetCode）

算法代码： class Solution { int m, n; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) { m = h.size(), n = h[0].size(); vector<vector<bool>> pac(m, vector<bool>(n)); vector<vector<bool>> atl(m, vector<bool>(n)); // 1. 先处理 pac 洋 for (int j = 0; j < n; j++) dfs(h, 0, j, pac); for (int i = 0; i < m; i++) dfs(h, i, 0, pac); // 2. 处理 atl 洋 for (int i = 0; i < m; i++) dfs(h, i, n - 1, atl); for (int j = 0; j < n; j++) dfs(h, m - 1, j, atl); vector<vector<int>> ret; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (pac[i][j] && atl[i][j]) ret.push_back({i, j}); return ret; } void dfs(vector<vector<int>>& h, int i, int j, vector<vector<bool>>& vis) { vis[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j]) dfs(h, x, y, vis); } } };

这段代码实现了一个经典的“太平洋大西洋水流问题”，使用了深度优先搜索（DFS）来标记能够同时流入太平洋和大西洋的区域。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个二维矩阵 h，其中 h[i][j] 表示位置 (i, j) 的高度。

水流可以从高处流向低处或相同高度。

要求找到所有能够同时流入太平洋和大西洋的位置。

太平洋位于矩阵的左边界和上边界，大西洋位于矩阵的右边界和下边界。

2. 代码思路初始化

dx 和 dy 数组用于表示四个方向的移动（上、下、左、右）。

m 和 n 分别表示矩阵的行数和列数。

pac 和 atl 是两个二维布尔数组，分别用于记录能够流入太平洋和大西洋的位置。

步骤 1：标记能够流入太平洋的位置

遍历矩阵的左边界和上边界，从这些位置开始进行 DFS，标记所有能够流入太平洋的位置。

使用 pac 数组记录这些位置。

步骤 2：标记能够流入大西洋的位置

遍历矩阵的右边界和下边界，从这些位置开始进行 DFS，标记所有能够流入大西洋的位置。

使用 atl 数组记录这些位置。

步骤 3：找到同时能够流入太平洋和大西洋的位置

遍历整个矩阵，找到同时被 pac 和 atl 标记的位置，将其加入结果集 ret。

DFS 函数

dfs 函数用于递归地标记与当前位置相连的所有能够流入海洋的位置。

将当前位置标记为已访问（vis[i][j] = true）。

遍历四个方向，如果相邻位置的高度大于等于当前位置的高度且未被访问过，则递归调用 dfs。

3. 代码实现细节边界遍历

分别遍历左边界、上边界、右边界和下边界，确保所有可能的起点都被处理。

DFS 的终止条件

在 dfs 函数中，通过检查坐标是否在矩阵范围内（x >= 0 && x < m && y >= 0 && y < n）来避免越界访问。

通过检查高度是否满足条件（h[x][y] >= h[i][j]）来确保水流能够流动。

结果集

使用 ret 数组存储所有满足条件的位置坐标。

4. 优化建议空间优化

可以直接修改 h 数组，使用额外的标记位来记录访问状态，从而省去 pac 和 atl 数组的空间开销。

例如，可以使用 h[i][j] 的符号位来标记访问状态。

广度优先搜索（BFS）

除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的矩阵。

5. 复杂度分析

时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。每个位置最多被访问两次（一次来自太平洋，一次来自大西洋）。

空间复杂度：O(m * n)，主要是 pac 和 atl 数组的空间开销。如果使用原地修改的方法，空间复杂度可以优化到 O(1)。

6. 总结

这段代码通过 DFS 遍历矩阵，有效地标记了能够流入太平洋和大西洋的位置。

通过分别处理两个海洋的边界，代码逻辑清晰且易于理解。

可以通过优化空间复杂度或使用 BFS 来进一步提升代码的效率。

六、529. 扫雷游戏 - 力扣（LeetCode）

算法代码： class Solution { int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1}; int m, n; public: vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) { m = board.size(), n = board[0].size(); int x = click[0], y = click[1]; if (board[x][y] == 'M') // 直接点到地雷 { board[x][y] = 'X'; return board; } dfs(board, x, y); return board; } void dfs(vector<vector<char>>& board, int i, int j) { // 统计⼀下周围的地雷个数 int count = 0; for (int k = 0; k < 8; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') { count++; } } if (count) // 周围有地雷 { board[i][j] = count + '0'; return; } else // 周围没有地雷 { board[i][j] = 'B'; for (int k = 0; k < 8; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') { dfs(board, x, y); } } } } };

这段代码实现了一个经典的“扫雷游戏”问题，使用了深度优先搜索（DFS）来模拟点击方块后的游戏逻辑。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个二维矩阵 board，表示扫雷游戏的初始状态：

'M' 表示未挖出的地雷。

'E' 表示未挖出的空白方块。

'B' 表示已挖出的空白方块，且周围没有地雷。

数字 '1' 到 '8' 表示已挖出的方块，且周围有对应数量的地雷。

'X' 表示已挖出的地雷。

给定一个点击位置 click，模拟点击后的游戏状态。

2. 代码思路初始化

dx 和 dy 数组用于表示八个方向的移动（上、下、左、右、左上、右上、左下、右下）。

m 和 n 分别表示矩阵的行数和列数。

点击逻辑

如果点击的位置是地雷（board[x][y] == 'M'），则将其修改为 'X'，表示游戏结束。

否则，调用 dfs 函数处理点击的方块。

DFS 函数

统计周围地雷数量：

遍历当前位置的八个方向，统计周围地雷的数量 count。

处理当前方块：

如果周围有地雷（count > 0），则将当前方块修改为地雷数量（count + '0'）。

如果周围没有地雷（count == 0），则将当前方块修改为 'B'，并递归处理周围的未挖出方块（'E'）。

3. 代码实现细节边界检查

在 dfs 函数中，通过检查坐标是否在矩阵范围内（x >= 0 && x < m && y >= 0 && y < n）来避免越界访问。

递归终止条件

如果当前方块是 'E'，则继续递归处理。

如果当前方块是 'M' 或其他非 'E' 的状态，则停止递归。

地雷数量统计

使用 count 变量统计周围地雷的数量，并将其转换为字符（count + '0'）以便更新方块状态。

4. 优化建议广度优先搜索（BFS）

除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的矩阵。

空间优化

代码已经直接修改了 board 数组，没有使用额外的空间，空间复杂度为 O(1)。

5. 复杂度分析

时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。每个位置最多被访问一次。

空间复杂度：O(m * n)，主要是递归调用栈的空间开销。如果使用 BFS，空间复杂度可以优化到 O(min(m, n))。

6. 总结

这段代码通过 DFS 遍历矩阵，模拟了扫雷游戏的点击逻辑。

通过统计周围地雷数量和递归处理空白方块，代码逻辑清晰且易于理解。

可以通过使用 BFS 或优化递归深度来进一步提升代码的效率。

七、LCR 130. 衣橱整理 - 力扣（LeetCode）

算法代码： class Solution { int m, n, k; bool vis[101][101]; int ret; int dx[4] = {0, 0, -1, 1}; int dy[4] = {1, -1, 0, 0}; public: int wardrobeFinishing(int _m, int _n, int _k) { m = _m, n = _n, k = _k; dfs(0, 0); return ret; } void dfs(int i, int j) { ret++; vis[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && check(x, y)) dfs(x, y); } } bool check(int i, int j) { int tmp = 0; while (i) { tmp += i % 10; i /= 10; } while (j) { tmp += j % 10; j /= 10; } return tmp <= k; } };

这段代码实现了一个经典的“机器人运动范围”问题，使用了深度优先搜索（DFS）来计算机器人能够到达的格子数量。下面是对代码的思路和实现细节的详细解释：

1. 问题描述

给定一个 m x n 的网格，机器人从 (0, 0) 出发。

机器人每次可以向上、下、左、右移动一格。

机器人不能进入行坐标和列坐标的数位之和大于 k 的格子。

要求计算机器人能够到达多少个格子。

2. 代码思路初始化

m 和 n 分别表示网格的行数和列数。

k 表示数位之和的上限。

vis 是一个二维布尔数组，用于记录每个位置是否已经被访问过。

ret 用于记录机器人能够到达的格子数量。

dx 和 dy 数组用于表示四个方向的移动（上、下、左、右）。