1. Toy模板网首页
  2. > Toy博客

【leetcode】floodfill算法

9月前 作者：2022horse 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了【leetcode】floodfill算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、图像渲染

1、题目描述

leetcode链接
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int m, n;
    int Init;
    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();
        Init = 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];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && Init == image[x][y])
            {
                dfs(image, x, y, color);
            }
        }
    }
};

3、解析

从(sr,sc)位置开始，先将该位置值覆盖掉，然后进行上下左右的顺序走，遇见走不通的路就回溯，直到走到原位置就停下即可。

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

二、岛屿数量

1、题目描述

leetcode链接
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    vector<vector<bool>> visit;
    int m, n;
    int ret; // 统计岛屿数量的
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size();
        n = grid[0].size();
        // 初始化visit数组
        visit = vector<vector<bool>>(m, vector<bool>(n));
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!visit[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)
    {
        // 标记当前坐标已经被访问过了
        visit[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && grid[x][y] == '1')
            {
                dfs(grid, x, y);
            }
        }
    }
};

3、解析

我们要明确一个点，是先要将该递归放在一个全局的视角去看待，并且要相信这个递归它是会自动回溯的，我们抱着这种想法来进行写下面的思路：

首先，我们先定义一个二维数组visit用来标记一下当前的位置是否被访问过，其次遍历这个二维数组，每遇到第一个1的时候先将数量进行加1，然后进入dfs深度优先遍历中，进入后，我们先定义其为true，也就是被访问过了，然后进行上下左右进行联通即可。

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

三、岛屿最大面积

1、题目描述

leetcode链接

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    vector<vector<bool>> visit;
    int m, n;
    int sum; // 统计最多数量
    int count; // 统计每个1的数量
    int maxAreaOfIsland(vector<vector<int>>& grid) 
    {
        m = grid.size();
        n = grid[0].size();
        visit = vector<vector<bool>>(m, vector<bool>(n));
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!visit[i][j] && grid[i][j] == 1)
                {
                    count = 0; // 每次进来先更新一下为0
                    dfs(grid, i, j);
                    sum = max(count, sum); // 取最大值
                }
            }
        }
        return sum;
    }
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    void dfs(vector<vector<int>>& grid, int i, int j)
    {
        visit[i][j] = true;
        count++; // 这里每次进来都要进行++，因为要避免回溯的情况
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && grid[x][y] == 1)
            {
                dfs(grid, x, y);
            }
        }
    }
};

3、解析

这道题的做法和上面一道题的基本框架一样的，无非就是每经过一个联通的岛屿其count都++，而这道题目必定是有诱惑人犯错的地方的，我在做这道题的时候其每次递归没有理解透彻导致只通过了部分样例，我们来分析一下我之前写的代码：
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

所以我们定一个全局的count变量，然后在每次进入1围成的岛屿中count都重新更新为0，然后再进入到dfs深度优先遍历函数进行递归，每次遇到一个1就++，并且进行标记当前位置被访问过了，剩下思路和上面一道题思路一样。

四、被围绕的区域

1、题目描述

2、代码

方法一：（用visit数组标记法）

class Solution 
{
public:
    // 全局变量
    vector<vector<bool>> visit;
    int m, n;
    void solve(vector<vector<char>>& board) 
    {
        m = board.size();
        n = board[0].size();
        visit = vector<vector<bool>>(m, vector<bool>(n));
        // 横着的
        for(int j = 0; j < n; j++)
        {
            if(!visit[0][j] && board[0][j] == 'O')
            {
                dfs(board, 0, j);
            }
            if(!visit[m - 1][j] && board[m - 1][j] == 'O')
            {
                dfs(board, m - 1, j);
            }
        }
        // 竖着的
        for(int i = 0; i < m; i++)
        {
            if(!visit[i][0] && board[i][0] == 'O')
            {
                dfs(board, i, 0);
            }
            if(!visit[i][n - 1] && board[i][n - 1] == 'O')
            {
                dfs(board, i, n - 1);
            }
        }
        // 遍历整个
        for(int i = 1; i < m - 1; i++)
        {
            for(int j = 1; j < n - 1; j++)
            {
                if(!visit[i][j] && board[i][j] == 'O')
                {
                    DFS(board, i, j);
                }
            }
        }
    }
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    // 给竖着的定义true即可
    void dfs(vector<vector<char>>& board, int i, int j)
    {
        visit[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }
    // 整体给改成X
    void DFS(vector<vector<char>>& board, int i, int j)
    {
        visit[i][j] = true;
        board[i][j] = 'X';
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y] == 'O')
            {
                DFS(board, x, y);
            }
        }
    }
};

方法二（修改值法）：

class Solution 
{
public:
    // 全局变量
    int m, n;
    void solve(vector<vector<char>>& board) 
    {
        m = board.size();
        n = board[0].size();
        // 横着的
        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);
            }
        }
        // 遍历整个
        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] == '.')
                {
                    board[i][j] = 'O';
                }
            }
        }
    }
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};

    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];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
            {
                dfs(board, x, y);
            }
        }
    }
};

3、解析

方法一的解析就很复杂，是需要用两个递归函数的，先把四周的围墙中的‘O’字符给全部标记已经访问过，然后横坐标从1这个位置到m-1这个位置，纵坐标从1这个位置到n-1这个位置进行找’O’这个字符，找到就进入DFS深度游优先变量这个函数进行递归，联通区全部改成’X’即可。

方法二的解析比较简单，只需要用到一个递归函数，同样先把四周围墙中的’O’改成’.‘，然后再遍历整个数组，将’.‘改成’O’，将’O’改成’X’即可。

五、太平洋大西洋水流问题

1、题目描述

leetcode链接

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    int m, n;
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    vector<vector<int>> ret;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        m = heights.size();
        n = heights[0].size();
        vector<vector<bool>> pac(m, vector<bool>(n));
        vector<vector<bool>> atl(m, vector<bool>(n));

        // 第一行--与pac洋有关
        for(int j = 0; j < n; j++)
        {
            dfs(heights, 0, j, pac);
        }
        // 第一列--与pac有关
        for(int i = 0; i < m; i++)
        {
            dfs(heights, i, 0, pac);
        }
        // 最后一行--与atl有关
        for(int j = 0; j < n; j++)
        {
            dfs(heights, m - 1, j, atl);
        }
        // 最后一列--与atl有关
        for(int i = 0; i < m; i++)
        {
            dfs(heights, i, n - 1, atl);
        }
        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>>& heights, int i, int j, vector<vector<bool>>& path)
    {
        path[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !path[x][y] && heights[i][j] <= heights[x][y])
            {
                dfs(heights, x, y, path);
            }
        }
    }
};

3、解析

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

我刚开始是用的是标记一个int类型的二维数组vector<vector< int >>，每次递归进行当前位置+1，发现不行，会越界，所以这个策略果断放弃。所以我们选择bool类型的两个二维数组，一个是太平洋二维数组，另一个是大西洋二维数组，我们只需要在递归时候标记已经被用过了，标记为true即可，然后最后进行遍历数组进行判断一下当前数组是不是两个洋都经过了即可。

六、扫雷游戏

1、题目描述

leetcode链接
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    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;
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
    {
        m = board.size();
        n = board[0].size();
        int i = click[0]; // 横坐标
        int j = click[1]; // 纵坐标
        if(board[i][j] == 'M')
        {
            board[i][j] = 'X';
            return board;
        }
        dfs(board, i, j);
        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];
            int 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];
                int y = j + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
                {
                    dfs(board, x, y);
                }
            }
        }
    }
};

3、解析

【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

七、衣柜整理

1、题目描述

leetcode链接
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝

2、代码

class Solution 
{
public:
    // 全局变量
    int dx[4] = {0, 0, -1, 1};
    int dy[4] = {1, -1, 0, 0};
    int sum;
    bool visit[101][101];
    int m, n, cnt;
    int wardrobeFinishing(int _m, int _n, int _cnt) 
    {
        m = _m;
        n = _n;
        cnt = _cnt;
        dfs(0, 0, cnt);
        return sum;
    }
    void dfs(int i, int j, int cnt)
    {
        sum++;
        visit[i][j] = true;
        for(int k = 0; k < 4; k++)
        {
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && check(x, y))
            {
                dfs(x, y, cnt);
            }
        }
    }
    bool check(int i, int j)
    {
        int tmp;
        while(i)
        {
            tmp += i % 10;
            i /= 10;
        }
        while(j)
        {
            tmp += j % 10;
            j /= 10;
        }
        return tmp <= cnt;
    }
};

3、解析

这道题目难度不大，但是最核心的问题是在于其是每个数位进行加减的，所以我们用到的是下面的将每一个数位进行加上的代码：
【leetcode】floodfill算法,C++刷题,算法,leetcode,c++,剪枝
其余算法原理实在是太简单了，不详细赘述了，直接看代码即可。文章来源地址https://www.toymoban.com/news/detail-833282.html

到了这里，关于【leetcode】floodfill算法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【贪心算法】leetcode刷题

    【贪心算法】leetcode刷题

    贪心算法无固定套路。 核心思想：先找局部最优，再扩展到全局最优。 两种思路： 1、从大到小。局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。 先遍历的胃口，在遍历的饼干 2、从小到大。 小饼干先喂饱小胃口 。两个

    2024年02月14日
    浏览(50)
  • 算法刷题记录-树(LeetCode)

    算法刷题记录-树(LeetCode)

    思路(DFS 中序遍历) 考虑中序遍历的性质即可 代码 思路(DFS) 对于一个节点是否删除，有如下几种情况: 思路（DFS） 首先，需要通过dfs算法找到从原点到目标点的路径。 p a t h = [ 2 , 3 , 5 , 7 ] path=[2,3,5,7] p a t h = [ 2 , 3 , 5 , 7 ] , k = 2 k=2 k = 2 。其中7为目标点然后考虑对路径的每一节

    2024年02月09日
    浏览(47)
  • 【算法专题】FloodFill 算法

    【算法专题】FloodFill 算法

    题目链接 - Leetcode -773.图像渲染 Leetcode -773.图像渲染 题目：有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。 你也被给予三个整数 sr, sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。 为了完成 上色工作 ，从初始像

    2024年02月03日
    浏览(35)
  • 【Leetcode刷题】算法：罗马数字转整数

    【Leetcode刷题】算法：罗马数字转整数

    定义一个 Solution 类，该类包含一个 romanToInt 方法用于将罗马数字转换为整数。 初始化变量 answer 为 0，用于保存转换后的整数值。 获取输入字符串 s 的长度，并保存在变量 length 中。 创建一个字典 d，将每个罗马数字字符与对应的数值进行映射。 使用 for 循环遍历 s 中的每个

    2024年02月05日
    浏览(92)
  • LeetCode高频算法刷题记录4

    LeetCode高频算法刷题记录4

    题目链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 参考题解：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/ 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“

    2024年02月06日
    浏览(60)
  • 数据结构算法leetcode刷题练习(1)

    数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ，找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • FloodFill算法---DFS

    FloodFill算法---DFS

    目录 floodfill算法概念： 算法模板套路：  例题1：图像渲染 例题2：岛屿数量 例题3：岛屿的最大面积 例题4：被围绕的区域 floodfill算法是一种常用的图像处理算法，用于填充连通区域。它从指定的种子点开始，将相邻的像素点按照某种条件进行填充，直到所有符合条件的像素

    2024年04月26日
    浏览(36)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

    算法刷题记录-双指针/滑动窗口(LeetCode)

    思路 根据题目描述，我们可以知道，如果要将某个单词定义为可扩张（stretchy），需要满足如下两个条件： 所以，我们在实现的时候，可以通过两个指针p1和p2，分别指向s和word，分别统计连续的相同字符数量c1和c2，然后再通过上述的两个条件进行判断，即：如果 则表示该单

    2024年02月09日
    浏览(43)

  • Java算法 leetcode简单刷题记录6

    环和杆： https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数： https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串： https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和： https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(46)

  • Java算法 leetcode简单刷题记录4

    买卖股票的最佳时机： https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 笨办法： 记录当天的值及之后的最大值，相减得到利润； 所有的天都计算下，比较得到利润最大值； 会超时 记录过程中遇到的最低值，每当有利润大于0及大于上一个利润值的情况，赋值； 最小和分割：

    2024年01月23日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包