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

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

article 2025/2/23 21:05:23

目录

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

 算法代码：

 算法思路

基础参数

函数入口

检查条件

初始化 BFS

BFS 填充过程

返回结果

复杂度分析

总结

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

算法代码： 

算法思路

基础参数

函数入口

遍历网格

BFS 遍历

返回结果

复杂度分析

总结

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

算法代码：

算法思路

基础参数

函数入口

遍历网格

BFS 遍历

返回结果

复杂度分析

总结

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

算法代码： 

算法思路

基础参数

函数入口

处理边界上的 'O' 区域

还原棋盘

BFS 遍历

复杂度分析

总结

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

 算法代码：

class Solution {
    typedef pair<int, int> PII; // 定义坐标对
    int dx[4] = {0, 0, 1, -1}; // 四个方向的x偏移量
    int dy[4] = {1, -1, 0, 0}; // 四个方向的y偏移量

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
                                   int color) {
        int prev = image[sr][sc]; // 获取起始点的原始颜色
        if (prev == color) // 如果目标颜色与原始颜色相同，直接返回
            return image;
        
        int m = image.size(), n = image[0].size(); // 获取图像的尺寸
        queue<PII> q; // 初始化队列
        q.push({sr, sc}); // 将起始坐标入队

        while (!q.empty()) { // BFS循环
            auto [a, b] = q.front(); // 获取队首元素
            image[a][b] = color; // 将当前点的颜色设为目标颜色
            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 && image[x][y] == prev) {
                    q.push({x, y}); // 将符合条件的坐标入队
                }
            }
        }
        return image; // 返回填充后的图像
    }
};

 算法思路

  1. 基础参数

    • 使用 typedef pair<int, int> PII 定义一个坐标对，方便存储和操作点的坐标。

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

  2. 函数入口

    • floodFill 函数接收一个图像 image（二维数组），起始坐标 sr 和 sc，以及要填充的颜色 color。

  3. 检查条件

    • 首先获取起始点的原始颜色 prev，如果该颜色已经是目标颜色 color，则直接返回原图像，避免不必要的操作。

  4. 初始化 BFS

    • 获取图像的尺寸 m 和 n。

    • 使用一个队列 q 来管理待处理的坐标。

    • 将起始坐标 (sr, sc) 入队。

  5. BFS 填充过程

    • 进入循环，直到队列为空：

      • 从队列中取出当前坐标 (a, b)。

      • 将该坐标的颜色设置为 color。

      • 遍历四个方向，计算相邻坐标 (x, y)。

      • 检查新坐标是否在图像范围内，以及该坐标的颜色是否与 prev 相同。如果满足条件，则将新坐标入队。

  6. 返回结果

    • 循环结束后，返回填充后的图像。

复杂度分析

  • 时间复杂度：O(N)，N 为图像中像素的总数。在最坏情况下，所有像素都可能被访问。

  • 空间复杂度：O(N)，队列在最坏情况下可能需要存储所有的像素。

总结

        这个实现有效地解决了洪水填充问题，通过广度优先搜索遍历所有与起始点相连的相同颜色区域并将其填充为目标颜色。可以根据需要调整该实现以适应更复杂的场景或者使用 DFS（深度优先搜索）来实现同样的功能。

 

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

算法代码： 

class Solution {
    int dx[4] = {1, -1, 0, 0}; // 表示上下左右的x偏移
    int dy[4] = {0, 0, 1, -1}; // 表示上下左右的y偏移
    bool vis[301][301]; // 记录访问状态
    int m, n; // 网格的行数和列数

public:
    int numIslands(vector<vector<char>>& 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 (grid[i][j] == '1' && !vis[i][j]) { // 找到一个新的岛屿
                    ret++; // 增加岛屿计数
                    bfs(grid, i, j); // 用BFS标记这个岛屿
                }
            }
        }
        return ret; // 返回岛屿总数
    }
    
    void bfs(vector<vector<char>>& grid, int i, int j) {
        queue<pair<int, int>> q; // 初始化队列
        q.push({i, j}); // 入队当前坐标
        vis[i][j] = true; // 标记为已访问
        while (q.size()) { // BFS循环
            auto [a, b] = q.front(); // 获取队首元素
            q.pop(); // 移除队首元素
            for (int k = 0; k < 4; k++) { // 遍历四个方向
                int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标
                // 检查是否在边界内，并且为 '1' 且未访问
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y]) {
                    q.push({x, y}); // 入队
                    vis[x][y] = true; // 标记为已访问
                }
            }
        }
    }
};

算法思路

  1. 基础参数

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

    • vis 数组用于标记已经访问过的网格，避免重复计算。

  2. 函数入口

    • numIslands 函数接收一个二维网格 grid 作为输入，返回岛屿的数量。

  3. 遍历网格

    • 计算网格的行数 m 和列数 n。

    • 使用双重循环遍历每个格子：

      • 当遇到 '1' 且未被访问过时，说明找到了一个新的岛屿，计数器 ret 加一，并调用 bfs 函数来遍历和标记这个岛屿的所有部分。

  4. BFS 遍历

    • 在 bfs 函数中：

      • 初始化一个队列，将当前陆地坐标入队，并将其标记为已访问。

      • 进入循环，直到队列为空：

        • 从队列中取出当前坐标 (a, b)。

        • 遍历四个方向，计算相邻坐标 (x, y)。

        • 检查新坐标是否在网格范围内，且该坐标为 '1' 且未被访问过。如果满足条件，则将新坐标入队并标记为已访问。

  5. 返回结果

    • 循环完成后，返回计数器 ret 的值，表示岛屿的总数量。

复杂度分析

  • 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

  • 空间复杂度：O(M * N)，用于存储访问状态 vis，在最坏情况下，可能需要存储整个网格的状态。

总结

        这个实现有效地解决了“岛屿数量”问题，通过广度优先搜索（BFS）遍历所有相连的陆地（'1'），并将其标记为已访问，以避免重复计数。可以根据需要将 BFS 替换为深度优先搜索（DFS）以实现相同的功能。总之，该算法能够高效地计算出网格中的岛屿数量，尤其适用于处理大型的二维网格问题。

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

算法代码：

class Solution {
    int dx[4] = {0, 0, 1, -1}; // 表示上下左右的x偏移
    int dy[4] = {1, -1, 0, 0}; // 表示上下左右的y偏移
    bool vis[51][51]; // 记录访问状态（假设最大网格为51x51）
    int m, n; // 网格的行数和列数

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 (grid[i][j] == 1 && !vis[i][j]) { // 找到一个新的岛屿
                    ret = max(ret, bfs(grid, i, j)); // 计算岛屿面积并更新最大面积
                }
            }
        }
        return ret; // 返回最大岛屿面积
    }
    
    int bfs(vector<vector<int>>& grid, int i, int j) {
        int count = 0; // 初始化当前岛屿面积计数
        queue<pair<int, int>> q; // 初始化队列
        q.push({i, j}); // 入队当前坐标
        vis[i][j] = true; // 标记为已访问
        count++; // 当前岛屿面积增加

        while (q.size()) { // BFS循环
            auto [a, b] = q.front(); // 获取队首元素
            q.pop(); // 移除队首元素
            for (int k = 0; k < 4; k++) { // 遍历四个方向
                int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标
                // 检查是否在边界内，并且为 '1' 且未访问
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
                    q.push({x, y}); // 入队
                    vis[x][y] = true; // 标记为已访问
                    count++; // 增加岛屿面积
                }
            }
        }
        return count; // 返回当前岛屿的面积
    }
};

算法思路

  1. 基础参数

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

    • vis 数组用于标记已经访问过的格子，以避免重复计算。

  2. 函数入口

    • maxAreaOfIsland 函数接收一个二维网格 grid 作为输入，返回最大的岛屿面积。

  3. 遍历网格

    • 计算网格的行数 m 和列数 n。

    • 使用双重循环遍历每个格子：

      • 当遇到 1（陆地）且未被访问过时，调用 bfs 函数来计算这个岛屿的面积，并更新最大面积 ret。

  4. BFS 遍历

    • 在 bfs 函数中：

      • 初始化一个计数器 count 用于记录岛屿的面积。

      • 将当前陆地坐标入队，并标记为已访问，同时将 count 增加。

      • 进入循环，直到队列为空：

        • 从队列中取出当前坐标 (a, b)。

        • 遍历四个方向，计算相邻坐标 (x, y)。

        • 检查新坐标是否在网格范围内，且该坐标为 1 且未被访问过。如果满足条件，则将新坐标入队并标记为已访问，同时增加 count。

  5. 返回结果

    • 循环完成后，返回最大的岛屿面积 ret。

复杂度分析

  • 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

  • 空间复杂度：O(M * N)，用于存储访问状态 vis，在最坏情况下，可能需要存储整个网格的状态。

总结

        这个实现有效地解决了“最大岛屿面积”问题，通过广度优先搜索（BFS）遍历所有相连的陆地（1），并计算其面积。该算法能够高效地找到最大的岛屿面积，尤其适用于处理大型的二维网格问题。如果需要，也可以将 BFS 替换为深度优先搜索（DFS）以实现相同的功能。总之，该算法能够在给定的网格中快速找到并计算最大岛屿的面积。

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

算法代码： 

class Solution {
    int dx[4] = {0, 0, 1, -1}; // 表示上下左右的x偏移
    int dy[4] = {1, -1, 0, 0}; // 表示上下左右的y偏移
    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') // 第一行
                bfs(board, 0, j);
            if (board[m - 1][j] == 'O') // 最后一行
                bfs(board, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') // 第一列
                bfs(board, i, 0);
            if (board[i][n - 1] == 'O') // 最后一列
                bfs(board, i, n - 1);
        }
        
        // 2. 还原剩余的区域
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') // 被围住的区域变为 'X'
                    board[i][j] = 'X';
                else if (board[i][j] == '.') // 安全的区域还原为 'O'
                    board[i][j] = 'O';
            }
        }
    }

    void bfs(vector<vector<char>>& board, int i, int j) {
        queue<pair<int, int>> q; // 初始化队列
        q.push({i, j}); // 入队当前坐标
        board[i][j] = '.'; // 将其标记为已访问（安全）

        while (q.size()) { // BFS循环
            auto [a, b] = q.front(); // 获取队首元素
            q.pop(); // 移除队首元素
            for (int k = 0; k < 4; k++) { // 遍历四个方向
                int x = a + dx[k], y = b + dy[k]; // 计算相邻坐标
                // 检查是否在边界内，并且为 'O'
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
                    q.push({x, y}); // 入队
                    board[x][y] = '.'; // 标记为已访问（安全）
                }
            }
        }
    }
};

算法思路

  1. 基础参数

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

    • m 和 n 分别表示棋盘的行数和列数。

  2. 函数入口

    • solve 函数接收一个二维棋盘 board，用于处理其中的 'O' 区域。

  3. 处理边界上的 'O' 区域

    • 通过双重循环遍历棋盘的边界（第一行、最后一行、第一列、最后一列）：

      • 当遇到 'O' 时，调用 bfs 函数，将其和与之相连的所有 'O' 修改为 '.'，表示这些 'O' 是安全的，不会被围住。

  4. 还原棋盘

    • 遍历整个棋盘，将剩余的 'O' （被围住的）改为 'X'，将 '.' 还原为 'O'。

  5. BFS 遍历

    • 在 bfs 函数中：

      • 初始化一个队列，将当前坐标入队，并将其改为 '.'。

      • 进入循环，直到队列为空：

        • 从队列中取出当前坐标 (a, b)。

        • 遍历四个方向，计算相邻坐标 (x, y)。

        • 检查新坐标是否在棋盘范围内，且该坐标为 'O'，如果满足条件，则将新坐标入队并改为 '.'。

复杂度分析

  • 时间复杂度：O(M * N)，其中 M 是行数，N 是列数。在最坏情况下，所有格子都可能被访问一次。

  • 空间复杂度：O(M * N)，用于存储队列和处理访问状态，尤其当整个棋盘都是 'O' 时，队列可能存储整个棋盘。

总结

        这个实现有效地解决了“被围绕的区域”问题，通过广度优先搜索（BFS）遍历所有与边界相连的 'O'，并将其标记为安全区域。最终，该算法能够高效地将被围住的区域转变为 'X'，而保证与边界相连的 'O' 区域保持不变。该算法非常适合处理类似的二维网格问题，通过 BFS 的方式可以灵活地处理不同的边界条件和连通性问题。


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

相关文章：

  • 神经网络八股（2）
  • Unity 位图字体
  • 3.1 actor基本框架（c#的Akka.Actor模式）
  • 约束性委派攻击和非约束性委派攻击
  • Vue 3 工程化：从理论到实践 （上篇）
  • DeepSeek在企业中的有那些具体应用？
  • 易基因： ChIP-seq+DRIP-seq揭示AMPK通过调控H3K4me3沉积和R-loop形成以维持基因组稳定性和生殖细胞完整性｜NAR
  • jvm中各个参数的理解
  • ROS 2机器人开发--第一个节点
  • HTTP SSE 实现
  • 【清华大学】DeepSeek从入门到精通完整版pdf下载
  • Could not initialize class io.netty.util.internal.Platfor...
  • nginx配置ssl
  • 《Spring实战》(第6版) 第3章 使用数据
  • 前端PDF转图片技术调研实战指南：从踩坑到高可用方案的深度解析
  • 基于Java爬虫获取1688商品分类信息（cat_get接口）的实现指南
  • 常用网络工具分析（ping，tcpdump等）
  • 如何平衡网络服务的成本、质量和可扩展性？
  • Nginx环境安装
  • 工业安卓主板在智慧粮仓设备中发挥着至关重要的作用