FloodFill算法---DFS

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

目录

floodfill算法概念:

算法模板套路: 

例题1:图像渲染

例题2:岛屿数量

例题3:岛屿的最大面积

例题4:被围绕的区域


floodfill算法概念:

floodfill算法是一种常用的图像处理算法,用于填充连通区域。它从指定的种子点开始,将相邻的像素点按照某种条件进行填充,直到所有符合条件的像素点都被填充为止。floodfill算法常用于图像处理中的填充、边界提取、区域分割等任务。它可以用于实现画图工具中的油漆桶工具,也可以用于图像分割中的区域填充。

floodfill算法的中文名为洪水灌溉算法,基本实现内容:从某个点开始向四周扩散,直到无法再扩散为止。(可以使用DFS和BFS,本文讲解DFS解决)从这个实现内容我们不难发现这很适合我们利用爆搜来实现(一般数据范围不会太大)。如下图数字为1的就是一个性质相同的连通块。这类问题通常会问我们1的最大联通块是多大?或者有几个1的连通块?使用floodfill算法解决的题目基本一眼就能看得出来,不想滑动窗口和动态规划之类的算法,你不试一试是看不出来要使用什么算法的😭😭😭。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

算法模板套路: 

创建所需的全局变量(最好设置为静态,因为非静态只有在leetcode上才行)

static boolean[][] vis;//( 不一定要有)

static int[ ] dx = {0 , 0 , 1 , -1 };

static int[ ] dy = {1 , -1 , 0 , 0 };

vis这个布尔类型数组来标记我们已经走过的路,防止重复走导致死循环。如果题目可以改给出的二维数组的值的话可以修改值就不用创建这个数组来标记了。

dx,dy数组配合使用,对应就是上下左右走,这是四个方向(上下左右)的,如果题目要求8个方向的话可以在草稿纸上画个图推一下很快的。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

其他的一些条件根据题目的具体情况创建。

DFS模板如下:

其中n为行的个数,m为列的个数,至于要不要回溯要根据题目要求什么来决定。如果是8个方向的话把改一下dx和dy还有k的值变为8即可。x >= 0 && x < n && y >= 0 && y < m 这个可以说是默写了,因为这就是防止越界,每道题目都是这么写的。

public static void dfs(int i,int j,.....){
        for(int k = 0;k < 4;k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >=0 && x < n && y >= 0 && y < m && !vis[x][y] && 题目条件){
                vis[x][y] = true;
                dfs(x,y,.....);
                vis[x][y] = false;//回溯
            }
        }
    }

上面的这些是作者自己总结出来的,友友们刚开始可以试试,后面做的熟练了基本写出这些就是肌肉记忆了,这个在比赛中也会考到。

下面给出的例题前三题必看,可以说是floodfill算法的经典题型了。

例题1:图像渲染

链接:图像渲染

有一幅以 m x n 的二维整数数组表示的图画 image ,其中 image[i][j] 表示该图画的像素值大小。

你也被给予三个整数 sr ,  sc 和 newColor 。你应该从像素 image[sr][sc] 开始对图像进行 上色填充 。

为了完成 上色工作 ,从初始像素开始,记录初始坐标的 上下左右四个方向上 像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应 四个方向上 像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为 newColor 。

最后返回 经过上色渲染后的图像 

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

详细题解: 

可以利用深搜,遍历到与该点相连的所有像素相同的点,然后将其修改成指定的像素即可。

这里再强调一下,在leetcode中不加static是可以的,但是在比赛中(要求自己写Main类)只能用static修饰的。 

直接对题目给出的一个点进行DFS,本题是直接在二位数组image的基础上直接修改那么就不用用到 vis 来标记了,因为走过的地方值被修改了那么就不会出现重复走的情况。具体代码如下:

class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int prev;
    int m,n;
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if(image[sr][sc] == color){
            return image;
        }
        prev = image[sr][sc];
        m = image.length;
        n = image[0].length;
        dfs(image,sr,sc,color);
        return image;
    }
    public void dfs(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 && image[x][y] == prev){
                dfs(image,x,y,color);
            }
        }
    }
}

例题2:岛屿数量

链接:岛屿数量

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

详细题解:

非常经典的一道floodfill算法题目其思路过程为:

遍历整个矩阵,每当找到一块陆地时,岛屿数量 + 1,并且将这个陆地相连的所有陆地,也就是这块岛屿,全部变成海洋。这样的话,我们下次遍历到这块岛屿的时候,它已经是海洋了,不会影响最终结果(当然也可以不修改矩阵,我们可以使用vis数组来完成去重操作)。变成海洋的操作可以利用DFS解决和上面给出的模板差不多😎😎😎

代码实现:

class Solution {
    static int ret;
    static boolean[][] vis;
    static int n;
    static int m;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};
    public static int numIslands(char[][] grid) {
        ret = 0;
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(grid[i][j] == '1' && !vis[i][j]){
                    dfs(grid,i,j);
                    ret++;
                }

            }
        }
        return ret;
    }
    public static void dfs(char[][] grid,int i,int j){
        vis[i][j] = true;
        for(int k = 0;k < 4;k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '1' && !vis[x][y]){
                dfs(grid,x,y);
            }
        }
    }
}

例题3:岛屿的最大面积

链接:岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

没错又是这张图因为比较经典且作者水平有限😭😭😭,所以就直接使用了。

详细题解:

遍历整个矩阵,每当遇到⼀块土地的时候,就用DFS将与这块土地相连的整个岛屿的面积计算出来。然后在搜索得到的所有岛屿面积中求一个最大值即可。这题我们就可以使用vis数组来标记这个位置是否已经被访问过了。

求这种最大值的又是深搜,建议大家自己设置一个变量来专门存储临时值和最大值,我一般存储临时值采用path,存储结果也就是最大值采用ret,step表示递归的层数(这个floodfill算法不涉及,在别的DFS题会用到)这个都行就是自己要明白。

class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    int ret;
    boolean[][] vis;
    int n,m;
    int path;
    public int maxAreaOfIsland(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        ret = 0;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(grid[i][j] == 1 && !vis[i][j]){
                    path = 0;
                    dfs(grid,i,j);
                    ret = Math.max(ret,path);
                }
            }
        }
        return ret;
    }
    public void dfs(int[][] grid,int i,int j){
        vis[i][j] = true;
        path++;
        for(int k = 0;k < 4;k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && 
            grid[x][y] == 1 && !vis[x][y]){
                dfs(grid,x,y);
            }
        }
    }
}

相信做完上面三道题目,友友们是不是觉得有点没有意思,感觉就是在考背诵一样,DFS的写法基本差不多,上面的只要根据题意稍加修改即可。其实DFS确实差不多,有些难点是在如何使用DFS而不是写出DFS,例如下面的例题四,运用到了我们解决问题的经典思路正难则反

例题4:被围绕的区域

链接:被围绕的区域

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法

可以看到如果我们不加以转换的话直接按照我们前面三题的思路来的话有点困难,因为要判断很多边界情况,且要进行两遍DFS,所以我们要想一种更为巧妙的解法:正难则反。

解题过程:

可以先利用dfs将与边缘相连的'0' 区域做上标记,然后重新遍历矩阵,将没有标记过的'0' 修改成'X' 即可。就是这么的简单。遍历边缘就画个图模拟一下即可,至于DFS的编写那还不是手到擒来🤩🤩🤩 ,具体代码如下:

class Solution {
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] vis;
    int n,m;
    public void solve(char[][] board) {
        n = board.length;
        m = board[0].length;
        vis = new boolean[n][m];
        //标记vis
        for(int i = 0;i < n;i++){
            if(board[i][0] == 'O'){
                dfs(board,i,0);
            }
            if(board[i][m - 1] == 'O'){
                dfs(board,i,m - 1);
            }
        }
        for(int i = 0;i < m;i++){
            if(board[0][i] == 'O'){
                dfs(board,0,i);
            }
            if(board[n - 1][i] == 'O'){
                dfs(board,n - 1,i);
            }
        }
        //将O用X填充
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++){
                if(board[i][j] == 'O' && !vis[i][j]){
                    board[i][j] = 'X';
                }
            }
        }
    }
    public void dfs(char[][] board,int i,int j){
        vis[i][j] = true;
        for(int k = 0;k < 4;k++){
            int x = i + dx[k];
            int y = j + dy[k];
            if(x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && 
            !vis[x][y]){
                dfs(board,x,y);
            }
        }
    }
}

总结:这类题难点在如何使用DFS,全局变量要根据具体情况来创建,这些搞定后写个DFS就是默写的事情。

结语:

其实写博客不仅仅是为了教大家,同时这也有利于我巩固知识点,和做一个学习的总结,由于作者水平有限,对文章有任何问题还请指出,非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注,这可以激励我写出更加优秀的文章。

FloodFill算法---DFS,算法,深度优先,算法,dfs,floodfill算法文章来源地址https://www.toymoban.com/news/detail-858633.html

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

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

领支付宝红包 赞助服务器费用

相关文章

  • 【算法详解 | DFS算法】深度优先搜索解走迷宫问题 | 深度优先图遍历

    by.Qin3Yu 本文需要读者掌握 结构体 和 栈 的操作基础,完整代码将在文章末尾展示。 特别声明:本文为了尽可能使用简单描述,以求简单明了,可能部分专有名词定义不准确。 栈相关操作可以参考我的往期博文: 【C++数据结构 | 栈速通】使用栈完成十进制数转二四八进制数

    2024年02月03日
    浏览(49)
  • 第一周算法训练(dfs)(深度优先搜索算法)

    dfs: 深度优先搜索算法 ,是一种用于遍历或 搜索树或图的算法 .沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被

    2024年02月20日
    浏览(49)
  • 图的遍历(搜索)算法(深度优先算法DFS和广度优先算法BFS)

    从图的某个顶点出发访问遍图中所有顶点,且每个顶点仅被访问一次。(连通图与非连通图) 1、访问指定的起始顶点; 2、若当前访问的顶点的邻接顶点有未被访问的,则任选一个访问之;反之,退回到最近访问过的顶点;直到与起始顶点相通的全部顶点都访问完毕; 3、若

    2024年01月17日
    浏览(46)
  • 如何实现一个简单的深度优先搜索(DFS)算法?

    前端入门之旅:探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅!这个专栏是为那些对Web开发感兴趣、刚刚踏入前端领域的朋友们量身打造的。无论你是完全的新手还是有一些基础的开发者,这里都将为你提供一

    2024年02月07日
    浏览(53)
  • DFS(深度优先搜索算法)入门保姆级超详解

    如题,本篇创作目的在于更精细化理解DFS的运作,篇幅不长,也只是作者的一家之言,只为提供一个对入门者的更精细的解释。 DFS,深度优先搜索算法,首先我们看中文,可以很清楚的理解到这个算法是指搜索操作中优先进行深度也就是纵向的数据筛查。 看搜索的基本思路

    2024年02月07日
    浏览(47)
  • Python算法:深度优先搜索—DFS(模板及其样例)

    • 沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。 • 并且每个节点只能访问一次。 • 本质上是持续搜索,遍历了所有可能的情况,必然能得到解。 • 流程是一个树的形式,每次一条路走到黑。 • 目的主要是达到被搜索结构的叶结点直到最后一层

    2024年03月24日
    浏览(48)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)两种算法c++

    深度优先搜索(DFS)和广度优先搜索(BFS)是一种用于遍历或搜索树图的一种算法,在这个过程中保证图或数的每个结点被访问且仅被访问一次,再按照每个结点访问的顺序不同分为深搜和广搜。 本文只讨论这两种算法在搜索方面的应用! 深度优先搜索 ( Depth-First-Search,DFS )它 沿

    2024年02月13日
    浏览(47)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(65)
  • 【C++算法】dfs深度优先搜索(上) ——【全面深度剖析+经典例题展示】

    💃🏼 本人简介:男 👶🏼 年龄:18 📕 ps:七八天没更新了欸,这几天刚搞完元宇宙,上午一直练🚗,下午背四级单词和刷题来着,还在忙一些学弟学妹录制视频和准备开学一些事,一直没空出时间来,等 20号练完车,也马上开学了QAQ。不过今天倒是空出来一些时间,恰好这

    2024年02月02日
    浏览(43)
  • 算法第六期——DFS初入门(深度优先搜索)(Python)

    目录   一、蛮力的技术:搜索 1.1、【暴力法】 1.2、蛮力的基本方法——扫描 二、搜索的基本方法 2.1、BFS:一群老鼠走迷宫 2.2、DFS:一只老鼠走迷宫  2.3、BFS和DFS的异同  三、DFS详解 3.1、DFS访问示例 3.2、 DFS基础: 递归和记忆化搜索 3.2.1 递归——斐波那契数列 3.2.2改进递归

    2024年04月13日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包