当前位置：首页 > article >正文

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

article 2025/3/3 20:13:11

一、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 数组用于表示四个方向的移动（上、下、左、右）。
DFS 函数
- 从起点 (0, 0) 开始调用 dfs 函数。
- 在 dfs 函数中：
  - 将当前位置标记为已访问（vis[i][j] = true），并增加 ret 的计数。
  - 遍历四个方向，如果相邻位置满足以下条件，则递归调用 dfs：
    - 在网格范围内（x >= 0 && x < m && y >= 0 && y < n）。
    - 未被访问过（!vis[x][y]）。
    - 数位之和不超过 k（check(x, y) 返回 true）。
检查函数
- check 函数用于计算位置 (i, j) 的行坐标和列坐标的数位之和。
- 如果数位之和不超过 k，则返回 true，否则返回 false。

3. 代码实现细节

边界检查
- 在 dfs 函数中，通过检查坐标是否在网格范围内（x >= 0 && x < m && y >= 0 && y < n）来避免越界访问。
数位之和计算
- 在 check 函数中，通过循环取模和除法操作计算行坐标和列坐标的数位之和。
访问标记
- 使用 vis 数组来避免重复访问已经处理过的格子。

4. 优化建议

广度优先搜索（BFS）
- 除了 DFS，还可以使用 BFS 来解决这个问题。BFS 使用队列来实现，适合处理较大的网格。
空间优化
- 可以直接修改 vis 数组，省去额外的空间开销。

5. 复杂度分析

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

6. 总结

这段代码通过 DFS 遍历网格，有效地计算了机器人能够到达的格子数量。
通过数位之和的限制和访问标记，代码逻辑清晰且易于理解。
可以通过优化空间复杂度或使用 BFS 来进一步提升代码的效率。

查看全文

http://www.kler.cn/a/566946.html

Win 11 C盘相邻的分区是恢复分区导致无法扩容

PDF文件转换为PNG图像

DH法建立6自由度机械臂正运动学模型

数据库设计报告

介绍一款飞算JavaAI编程工具，集成到idea，图文并茂

Graph Convolutional Networks(GCN)图卷积网络

解释 Node.js 中的异步编程模型，如何使用回调、Promise 和async / await 处理异步操作？

PyCharm Python 环境配置指南

HTTP3.0 和 HTTP2.0，HTTP1.0区别

前端存储方案全面对比：localStorage、sessionStorage、cookies与IndexedDB

【开发知识点一】随机数生成器 /dev/urandom 和 /dev/random

第一届启航杯-web-misc（全）

如何查看react的版本号

如何长期保存数据（不包括云存储）最安全有效？

决策树：机器学习中的分类与回归利器

LabVIEW 无法播放 AVI 视频的编解码器解决方案

Unclutter for Mac v2.2.12 剪贴板/文件暂存/笔记三合一支持M、Intel芯片

jenkins使用插件在Build History打印基本信息

DeepSeek 开源周五个开源项目，引领 AI 创新？

leetcode---LCR 123.图书整理1

一、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. 代码实现细节

边界遍历

代码思路

问题描述

算法选择

代码结构

代码详解

1. 成员变量

2. `floodFill` 函数

参数：

逻辑：

3. `dfs` 函数

参数：

逻辑：

代码优化

边界检查优化

使用 BFS

空间优化

示例运行

总结

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