【算法】bfs与dfs算法解决FloodFill问题（C++）

news/2024/7/20 21:57:48 标签: 算法, 宽度优先, 深度优先

文章目录

  • 1. 什么是FloodFill问题
  • 2. 用什么方法解决FloodFill问题
  • 3. 具体例题
    • [733. 图像渲染](https://leetcode.cn/problems/flood-fill/description/)
    • [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/description/)
    • [695. 岛屿的最大面积](https://leetcode.cn/problems/max-area-of-island/submissions/488395008/)
    • [130. 被围绕的区域](https://leetcode.cn/problems/surrounded-regions/description/)

1. 什么是FloodFill问题

一般floodfill问题可以描述为：给定一个二维矩阵，其中每个元素代表一个像素点，并给定一个起始点、目标颜色和填充颜色。问题要求将以起始点为中心，与其相邻且具有相同颜色的所有区域都填充为目标颜色。

在这里插入图片描述

2. 用什么方法解决FloodFill问题

我们通常使用下面两种方法解决FloodFill算法问题：

DFS（深搜） 算法通常使用递归实现，在处理当前像素点的相邻像素点时，递归调用 DFS 函数，不断深入直到无法找到相邻像素为止。

BFS （宽搜）算法通常使用队列实现，将起始像素点加入队列中，并不断扩展队列中的像素点，直到队列为空为止。

下面直接结合例题来理解两种解题方法。

3. 具体例题

第一道题 “图像渲染” 是下面例题中作为基座的一道题，讲解会尽量详细，后面的题

733. 图像渲染

在这里插入图片描述

题意分析

即对于一个矩阵，我们随机选取一个元素，将该元素与对于其有相同值的上下左右 的元素（对上下左右的元素继续找上下左右） 均上色为color。本质上就是找区域内的相邻元素。

解法

DFS（深度优先搜索）

“搜索一个位置的上下左右坐标，并对其上下左右坐标继续搜索上下左右坐标” 的过程可以理解为将一个主问题分解为多个子问题的过程，适用递归解决。

我们知道：深度优先搜索即一条路走到死，而该递归过程也是深搜的思想。

在这里插入图片描述

思路

  1. 先记录题目给我们的当前位置的颜色prevColor，如果当前位置=color，则直接返回
  2. 以当前位置开始，直接进行递归操作
    • 对于递归函数：先将当前位置上色，随后遍历上下左右四个方向的元素，每遍历到一个元素
    • 对该元素进行进行dfs操作，即可完成对 相连像素点的上色

代码

class Solution {
private:
    int dx[4] = {0, 0, -1, 1}; // 用于计算上下左右位置的下标
    int dy[4] = {-1, 1, 0, 0};
    int m, n, _color, prevColor; // 定义成全局变量方便调用（也可以传参）

    // dfs: 查看 坐标(x, y) 上下左右四个元素，并更改颜色
    void dfs(vector<vector<int>>& image, int x, int y) {
        image[x][y] = _color; // 当前位置上色
        for(int k = 0; k < 4; ++k) {
            int nx = x + dx[k]; // 计算一个方向的坐标
            int ny = y + dy[k];
            // 确保不越界 以及 值相同
            if(nx >= 0 && nx < m && ny >= 0 && ny < n && image[nx][ny] == prevColor)
                dfs(image, nx, ny); // 递归找连结的需要上色的像素
        }
    }

public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        prevColor = image[sr][sc]; // 记录最开始 / 当前元素颜色
        if(prevColor == color) return image; // 如果当前像素已经是所需颜色，则直接返回矩阵

        m = image.size(), n = image[0].size();
        _color = color;

        dfs(image, sr, sc);

        return image;
    }
};

BFS（宽度优先搜索）

宽度优先搜索利用队列和循环，每次将坐标入队，随后将其上下左右四个坐标入队，通过每次取队列元素，持续该过程，直到队列为空在这里插入图片描述

思路

  1. 先记录当前位置的颜色prevColor，如果当前位置=color，则直接返回
  2. 将当前位置坐标入队，每次提取当前元素的坐标，并将其上色
  3. 将上下左右四个方向的元素（符合条件的）入队，重复此过程

代码

class Solution {
public:
    typedef pair<int, int> pii;
    int dx[4] = {0, 0, -1, 1}; // 查询当前像素的上下左右时，xy坐标的更改
    int dy[4] = {-1, 1, 0, 0};

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        // 边界情况
        int tmp = image[sr][sc]; // 记录要更改的像素值
        if(tmp == color) return image;
        
        queue<pii> q; // 存储像素坐标
        q.push({sr, sc});
        while(!q.empty())
        {
            auto [a, b] = q.front(); // 提取当前像素坐标
            q.pop();
            image[a][b] = color; // 上色（更改像素值）
            for(int i = 0; i < 4; ++i)
            {
                int x = a + dx[i];
                int y = b + dy[i];
                // 如果未越界则入队
                if(x >= 0 && x < image.size() && y >= 0 && y < image[0].size() && image[x][y] == tmp)
                    q.push({x, y});
            }
        }

        return image;
    }
};

200. 岛屿数量

在这里插入图片描述
题意分析

矩阵由’1’, ‘0’ 两个元素组成，每一块相连的1（横着竖着相连）组成的区域为一个岛屿，我们需要找到矩阵中岛屿的数量。

解法

DFS（深度优先搜索）

思路

  1. 首先我们定义visit数组，用于记录矩阵中每一位元素是否已经被遍历过，如果为true，则不去执行该位的操作。
  2. 遍历整个矩阵，对于矩阵的每个（符合要求的）元素都执行dfs算法
  3. 每次循环中dfs彻底结束，则统计出了一片岛屿，++ret（最终结果）
  4. 关于此题的dfs：
    • 用于将矩阵中坐标为（x, y）的元素及其上下左右的元素标记

代码

class Solution {
private:
    int ret = 0; // 定义为全局变量，方便dfs改动和调用
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    vector<vector<bool>> visit; // 存储网格是否被检索过的信息

private:
    // 通过递归，将当前位置的岛屿统计出来
    // dfs： 将grid[x][y] 位置所在的岛屿统计出来
    void dfs(vector<vector<char>>& grid, int x, int y) {
        // 将当前位置检索设置为true
        visit[x][y] = true;
        for(int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if((nx >= 0 && nx < m) && (ny >= 0 && ny < n) && !visit[nx][ny] && grid[nx][ny] == '1')
            {
                dfs(grid, nx, ny);
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        visit.resize(m, vector<bool>(n, false)); // 初始化visit数组
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(!visit[i][j] && grid[i][j] == '1') // 该位置并未检索过且值为1
                {
                    ++ret;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
};

BFS（宽度优先搜索）

思路

  1. 这里宽搜和深搜的代码非常相似，只需要将bfs代码内部将递归改为使用队列即可，具体代码中注解，不再多余解释

代码

class Solution {
public:
    int ret = 0;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;
    vector<vector<bool>> visit; // 存储网格是否被检索过的信息

    void bfs(vector<vector<char>>& grid, int x, int y) {
        queue<pair<int, int>> q; // 存储位置坐标
        
        q.push({x, y});
        while(!q.empty())
        {
            auto [a, b] = q.front(); // 取出队头元素
            q.pop();
            for(int k = 0; k < 4; ++k) // 遍历该位置的上下左右四个位置
            {
                int nx = a + dx[k];
                int ny = b + dy[k];
                if((nx >= 0 && nx < m) && (ny >= 0 && ny < n) && !visit[nx][ny] && grid[nx][ny] == '1')
                {
                    q.push({nx, ny});
                    visit[nx][ny] = true;
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        visit.resize(m, vector<bool>(n, false));

        // 遍历矩阵
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(!visit[i][j] && grid[i][j] == '1')
                {
                    ++ret;
                    bfs(grid, i, j);
                }
            }
        }

        return ret;
    }
};

695. 岛屿的最大面积

在这里插入图片描述

题意分析

该题和上一题（岛屿数量）在解法和思路上可以说非常相似，只是前者要求岛屿数量，而后者要求岛屿最大面积，我们只需定义一个变量，每次统计一个岛屿后比较并更新该变量即可。

解法

DFS（深度优先搜索）

思路

重复：该题和上一题（岛屿数量）在解法和思路上可以说非常相似，只是前者要求岛屿数量，而后者要求岛屿最大面积，我们只需定义一个变量，每次统计一个岛屿后比较并更新该变量即可。

所以重点在于ret何时统计：

  1. 对于深搜，我们每次执行当前递归函数彻底结束后，执行ret = max(count, ret);即更新最大面积。
  2. 因为递归函数结束后，此时count记录的就是新岛屿的面积，则在dfs后更新最大面积。

代码

class Solution {
private:
    vector<vector<bool>> visit;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int ret = 0, count = 0; // 统计岛屿面积
    int m, n;

public:
    void dfs(vector<vector<int>>& grid, int x, int y) {
        visit[x][y] = true; // 将当前位置检索设置为true
        for(int k = 0; k < 4; ++k)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if((nx >= 0 && nx < m) && (ny >= 0 && ny < n) && !visit[nx][ny] && grid[nx][ny] == 1) // 判断是否合法
            {
                ++count;
                dfs(grid, nx, ny);
            }
        }   
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        visit.resize(m, vector<bool>(n, false));

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                count = 1; // 当前位置开始（从1开始）
                if(!visit[i][j] && grid[i][j] == 1)
                {
                    dfs(grid, i, j);
                    ret = max(count, ret); // 找到最大面积
                }
            }
        }

        return ret;
    }
};

BFS（宽度优先搜索）

思路

ret何时统计：

  1. 对于宽搜，我们每次执行一次bfs函数后，进行ret = max(ret, count),
  2. 因为执行dfs后，count的值就是新岛屿的面积，所以我们在其后判断更新最大面积。

代码

class Solution {
private:
    typedef pair<int, int> pii;
    vector<vector<bool>> visit;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int ret = 0, count = 0; // 统计岛屿面积
    int m, n;

public:
    void bfs(vector<vector<int>>& grid, int x, int y) {
        visit[x][y] = true; // 将当前位置检索设置为true
        queue<pii> q; // 队列存储坐标
        q.push({x, y}); // 将起始坐标添加到队列中
        while(!q.empty()) // 广度优先搜索
        {
            auto [x, y] = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if((nx >= 0 && nx < m) && (ny >= 0 && ny < n) && !visit[nx][ny] && grid[nx][ny] == 1) // 判断是否合法
                {
                    ++count;
                    visit[nx][ny] = true;
                    q.push({nx, ny}); // 将新的岛屿坐标添加到队列中
                }
            }
        }   
    }

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        visit.resize(m, vector<bool>(n, false));

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                count = 1; // 当前位置开始（从1开始）
                if(!visit[i][j] && grid[i][j] == 1)
                {
                    bfs(grid, i, j);
                    ret = max(ret, count);
                }
            }   
        }

        return ret;
    }
};

130. 被围绕的区域

在这里插入图片描述

题意分析

  1. 题目要求我们找到所有被’X’围绕的’O’，并将其改为’X’
    • 被’X’围绕的’O’：
  2. 正难则反：我们直接找到被’X’围绕的’O’是有难度的，则可以逆转思维：
    • 找到所有不被’X’包围的’O’，将这些’O’改为’T’（改成任意字符）
    • 随后遍历矩阵，将所有’O’改为’X’，此时即完成了题目要求
    • 最后将’T’再改回X即可

在这里插入图片描述

解法

DFS（深度优先搜索）

思路

  1. 根据题意分析的思路讲解，首先遍历矩阵四边，对边缘元素执行dfs函数
    • dfs: 用于将当前位置联结的’O’改为’T’
  2. 当 循环+dfs 全部执行完毕，此时四边相连的’O’已经被改为’T’
  3. 遍历矩阵，将剩余的’O’改为’X’，将’T’改为’O’。

代码

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    int m, n;

    // dfs将当前位置周围的'O'改为'T'
    void dfs(vector<vector<char>>& board, int x, int y) {
        board[x][y] = 'T';
        for(int k = 0; k < 4; ++k)
        {
            int a = x + dx[k];
            int b = y + dy[k];
            if((a >= 0 && a < m) && (b >= 0 && b < n) && board[a][b] == 'O') // 保证合法性
            {
                dfs(board, a, b);
            }
        }
    }

    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();

        // 正难则反（将未被'X'围绕的'O'更改，然后遍历矩阵找'O'）
        // 1. 矩阵四边周围的'O' 改为 'T'
        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);
        }
        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);
        }

        // 2. 还原：将'O'改为'X' / 将'T'改为'O'
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'T') board[i][j] = 'O';
            }
        }
    }
};

BFS（宽度优先搜索）

思路

和前面的题一致，我们用队列进行宽搜的实现：

  1. 首先创建visit数组，用于记录矩阵中的每位是否被遍历过
  2. 除了bfs函数思路不同，其余与dfs完全一致，这里主要在于bfs的写法：
    • 先将当前位置入队，并在visit中改为true
    • 只要队列不为空，持续获取上下左右方向的元素，符合要求的入队更改为true，持续此过程。

代码

class Solution {
public:
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {-1, 1, 0, 0};
    vector<vector<bool>> visit;
    int m, n;

    // bfs将当前位置周围的'O'改为'T'
    void bfs(vector<vector<char>>& board, int x, int y) {
        queue<pair<int, int>> q;
        visit[x][y] = true;
        board[x][y] = 'T';
        q.push({x, y}); // 将起始位置入队
        while(!q.empty())
        {
            auto [x, y] = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + dx[k];
                int ny = y + dy[k];
            if((nx >= 0 && nx < m) && (ny >= 0 && ny < n) && !visit[nx][ny] && board[nx][ny] == 'O')
                {
                    board[nx][ny] = 'T'; // 将'O'改为'T'
                    visit[nx][ny] = true; // 修改为单等号
                    q.push({nx, ny});
                }
            }
        }
    }

    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        visit.resize(m, vector<bool>(n, false)); // bfs算法中记录该位置是否被检查过

        // 正难则反（将未被'X'围绕的'O'更改，然后遍历矩阵找'O'）
        // 1. 矩阵四边周围的'O' 改为 'T'
        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);
        }
        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);
        }

        // 2. 还原：将'O'改为'X' / 将'T'改为'O'
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == 'T') board[i][j] = 'O';
            }
        }
    }
};

http://www.niftyadmin.cn/n/5269240.html

相关文章

Mybatis中的${}和#{}区别

Mybatis中的${}和#{}区别

前言 动态 sql 是 mybatis 的主要特性之一&#xff0c;在 mapper 中定义的参数传到 xml 中之后&#xff0c;在查询之前&#xff0c; mybatis 会对其进行动态解析。mybatis 为我们提供了两种支持动态 sql 的语法&#xff1a;#{}以及${} 提示&#xff1a;以下是本篇文章正文内容…
阅读更多...
linux 阻塞io

linux 阻塞io

睡眠的介绍 对于一个进程"睡眠"意味着什么? 当一个进程被置为睡眠, 它被标识为处于一个特殊的状 态并且从调度器的运行队列中去除. 直到发生某些事情改变了那个状态, 这个进程将不被 在任何 CPU 上调度, 并且, 因此, 将不会运行. 一个睡着的进程已被搁置到系统的一…
阅读更多...
论文阅读：Learning sRGB-to-Raw-RGB De-rendering with Content-Aware Metadata

论文阅读：Learning sRGB-to-Raw-RGB De-rendering with Content-Aware Metadata

论文阅读&#xff1a;Learning sRGB-to-Raw-RGB De-rendering with Content-Aware Metadata Abstract 大多数的 Camera ISP 会将 RAW 图经过一系列的处理&#xff0c;变成 sRGB 图像&#xff0c;ISP 的处理中很多模块是非线性的操作&#xff0c;这些操作会破坏环境光照的线性…
阅读更多...
CGAL的手柄和循环器

CGAL的手柄和循环器

1、手柄 CGAL中的大多数数据结构在其用户界面中使用Handles 的概念来引用它们存储的元素。这个概念描述了有时被称为琐碎迭代器的东西。Handle类似于指向对象的指针&#xff0c;提供解引用运算符*&#xff08;&#xff09;和成员访问运算符->&#xff08;&#xff09;&#…
阅读更多...
Linear probing accuracy（线性探测精度）是什么？

Linear probing accuracy（线性探测精度）是什么？

"Linear probing accuracy" 是一种评估自监督学习&#xff08;Self-Supervised Learning, SSL&#xff09;模型性能的方法。在这种方法中&#xff0c;使用一个简单的线性分类器&#xff08;通常是一个线性层或者一个全连接层&#xff09;来测试模型学习到的特征的质量…
阅读更多...
《地理信息系统原理》笔记/期末复习资料（11. GIS的输出与地图可视化）

《地理信息系统原理》笔记/期末复习资料（11. GIS的输出与地图可视化）

目录 11. GIS的输出与地图可视化 11.1. GIS的输出 11.1.1. 输出方式 11.1.2. GIS的图形输出设备 11.2. 地图符号 11.2.1. 地图符号的实质 11.2.2. 地图符号的分类 11.2.3. 地图符号的设计要求 11.3. 专题信息表达 11.3.1. 专题地图的基本概念 11.3.2. 专题地图的表示…
阅读更多...
Wordpress modown8.8.1主题学习版开心版

Wordpress modown8.8.1主题学习版开心版

Modown是模板兔基于Erphpdown wordpress下载插件开发的付费下载资源、付费下载源码、收费附件下载、付费阅读查看隐藏内容、团购下载的WordPress主题&#xff0c;本站提供Modown主题开心版&#xff0c;免授权使用&#xff0c;仅用于个人学习&#xff0c;禁止用于商业用途&#…
阅读更多...
Aurora8B10B(二) 从手册和仿真学习Aurora8B10B

Aurora8B10B(二) 从手册和仿真学习Aurora8B10B

一. 简介 在上篇文章中&#xff0c;主要结合IP配置界面介绍了一下Aurora8B10B&#xff0c;这篇文章将结合文档来学习一下Aurora8B10B内部的一些细节 和 相关的时序吧。文档主要是参考的是这个 pg046-aurora-8b10b-en-us-11.1 二. Aurora8B10B内部细节 在手册上&#xff0c;对…
阅读更多...
最新文章

Copyright @ 2022~2023