FloodFill算法就是用来寻找性质相同的连通快的算法这篇博客都是用dfs来实现FloodFill算法1.图像渲染题目链接733. 图像渲染 - 力扣LeetCode题目解析将和sr,sc相连的所有像素相同的点将这些点的值都修改为目标值算法讲解利用深搜遍历所有与初始点相连的所有像素相同的点然后将其修改成指定的像素值即可代码实现一个小细节如果colorimage[sr][sc]此时就不用去遍历image了此时直接返回image即可或者也可以创建一个check的boolean类型的数组去标记已经访问的位置//第一种写法 class Solution { int h,l,prev; int[] dx{0,0,1,-1}; int[] dy{1,-1,0,0}; public int[][] floodFill(int[][] image, int sr, int sc, int color) { himage.length; limage[0].length; previmage[sr][sc]; if(prevcolor) return image; dfs(image,sr,sc,color); return image; } public void dfs(int[][] image,int i,int j,int color){ image[i][j]color; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl image[x][y]prev){ dfs(image,x,y,color); } } } } //第二种写法 class Solution { int h,l,prev; int[] dx{0,0,1,-1}; int[] dy{1,-1,0,0}; boolean[][] check; public int[][] floodFill(int[][] image, int sr, int sc, int color) { himage.length; limage[0].length; checknew boolean[h][l]; previmage[sr][sc]; dfs(image,sr,sc,color); return image; } public void dfs(int[][] image,int i,int j,int color){ image[i][j]color; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl image[x][y]prev check[x][y]false){ check[x][y]true; dfs(image,x,y,color); check[x][y]false; } } } }2.岛屿数量题目链接200. 岛屿数量 - 力扣LeetCode题目解析计算岛屿的数量也就是计算grid数组中数字为1的连通快的个数算法讲解 FloodFill首先要创建一个同等规模的check的boolean数组先遍历一遍grid数组当遇到1时且该对应的check[i][j]false就通过dfs递归函数将这个位置的上下左右中为1的位置的对应到check数组中的值改为true即可代码实现class Solution { boolean[][] check; int h,l; int[] dx{0,0,-1,1}; int[] dy{-1,1,0,0}; public int numIslands(char[][] grid) { hgrid.length; lgrid[0].length; int ret0; checknew boolean[h][l]; for(int i0;ih;i){ for(int j0;jl;j){ if(grid[i][j]1check[i][j]false){ ret; dfs(grid,i,j); } } } return ret; } public void dfs(char[][] grid,int i,int j){ check[i][j]true; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl check[x][y]false grid[x][y]1){ dfs(grid,x,y); } } } }3.岛屿的最大面积题目解析返回最大岛屿的面积算法讲解FloodFill依旧是对grid数组做一遍深度优先遍历当遇到1时就上下左右去寻找连通的1且创建一个全局变量area去记录每一次递归时找到的岛屿的面积代码实现代码细节每次递归之前要将area置为0因为每一次递归都是去找新的岛屿计算新的岛屿的面积之前要将之前计算的岛屿的面积去掉也就是将area置为0class Solution { boolean[][] vis; int h,l,area,ret; int[] dx{0,0,1,-1}; int[] dy{1,-1,0,0}; public int maxAreaOfIsland(int[][] grid) { hgrid.length; lgrid[0].length; visnew boolean[h][l]; for(int i0;ih;i){ for(int j0;jl;j){ if(grid[i][j]1vis[i][j]false){ area0;//小细节 dfs(grid,i,j); retMath.max(ret,area); } } } return ret; } public void dfs(int[][] grid,int i,int j){ area; vis[i][j]true; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl grid[x][y]1 vis[x][y]false){ dfs(grid,x,y); } } } }4.被围绕的区域题目链接130. 被围绕的区域 - 力扣LeetCode题目解析将矩阵中的被X围绕的连通O区域中的字母全部改为字母X算法讲解FloodFill这道题的难点就是在于处理位于边界的连通O区域如果我们直接对矩阵进行一遍深度遍历那马就要写两个dfs函数一个用来处理内部的O区域另一个用来处理处于边界的O区域但是这样写是在是太复杂了正难则反我们可以先去处理边界的情况先将位于边界的连通O区域全部改为字符点处理完边界情况之后在去遍历矩阵遇到字符点则就将其还原成O此时如果遇到O那么此时的O区域肯定是合法的此时直接将O改为X即可代码实现class Solution { int h,l; int[] dx{0,0,1,-1}; int[] dy{1,-1,0,0}; public void solve(char[][] board) { hboard.length; lboard[0].length; for(int j0;jl;j){ if(board[0][j]O) dfs(board,0,j); if(board[h-1][j]O) dfs(board,h-1,j); } for(int i0;ih;i){ if(board[i][0]O) dfs(board,i,0); if(board[i][l-1]O) dfs(board,i,l-1); } for(int i0;ih;i){ for(int j0;jl;j){ if(board[i][j].) board[i][j]O; else if(board[i][j]O) board[i][j]X; } } } public void dfs(char[][] board,int i,int j){ board[i][j].; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl board[x][y]O){ dfs(board,x,y); } } } }5.太平洋大西洋流水问题题目链接417. 太平洋大西洋水流问题 - 力扣LeetCode题目解析找出矩阵中既能流入太平洋和大西洋的位置解法一直接暴搜直接遍历矩阵直接对每一个位置进行一遍FloodFill但是这样会出现重复走大量的重复路径代码可能会超时解法二正难则反我们可以转换一下思路题目要求我们找出既能流入太平洋又能流入大西洋的位置可以反过来思考从太平洋或者大西洋能流入矩阵的哪一些位置此时创建两个同等规模的boolean类型的数组paci和atla如果paci[i][j]或者atla[i][j]的值为true那么就代表从太平洋或者大西洋的水能流入ij位置当paci[i][j]和atla[i][j]的值同时为true时就代表太平洋和大西洋的水都能能流入ij位置此时对分别对第一行和第一列最后一行和最后一列分别进行一遍FloodFill即可代码实现class Solution { ListListInteger ret; int h,l; int[] dx{0,0,1,-1}; int[] dy{1,-1,0,0}; public ListListInteger pacificAtlantic(int[][] heights) { hheights.length; lheights[0].length; boolean[][] pacinew boolean[h][l]; boolean[][] atlanew boolean[h][l]; retnew ArrayList(); //处理太平洋 //第一行 for(int j0;jl;j) dfs(heights,0,j,paci); //第一列 for(int i0;ih;i) dfs(heights,i,0,paci); //处理大西洋 //最后一行 for(int j0;jl;j) dfs(heights,h-1,j,atla); //最后一列 for(int i0;ih;i) dfs(heights,i,l-1,atla); for(int i0;ih;i){ for(int j0;jl;j){ if(paci[i][j]trueatla[i][j]true){ ListInteger tmpnew ArrayList(); tmp.add(i); tmp.add(j); ret.add(tmp); } } } return ret; } public void dfs(int[][] heights,int i,int j,boolean[][] ocean){ ocean[i][j]true; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl heights[x][y]heights[i][j] ocean[x][y]false){ dfs(heights,x,y,ocean); } } } }6.扫雷游戏题目链接529. 扫雷游戏 - 力扣LeetCode题目解析就是扫雷游戏的规则点击一个为挖出的方块则与这个空格相连的空格也会被展开如果某一个空格的相邻有地雷的花就不展开与这个空格相邻的空格只需要将这个空格的值改为地雷的数量即可算法讲解FloodFill这道题就是对棋盘从点击的位置进行一遍深度遍历即可如果遇到为挖出的空格则将其翻转即可但是如果未挖出的空格相邻位置有地雷将这个空格的值改为地雷的数量则此时dfs函数就是用来翻转空格的但是翻转的情况有两种如果空格的相邻位置没有地雷将M改为B即可如果空格的相邻位置有地雷要将M给为地雷的数量所以此时在递归之前要对地雷的数量进行一个判断代码实现class Solution { int h,l; int[] dx{0,0,-1,1,-1,-1,1,1}; int[] dy{-1,1,0,0,-1,1,-1,1}; public char[][] updateBoard(char[][] board, int[] click) { hboard.length; lboard[0].length; int xclick[0]; int yclick[1]; if(board[x][y]M){ board[x][y]X; return board; } dfs(board,x,y); return board; } public void dfs(char[][] board,int i,int j){ //判断地雷的数量 int count0; for(int k0;k8;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl board[x][y]M){ count; } } if(count0){ board[i][j]B; for(int k0;k8;k){ int xidx[k]; int yjdy[k]; if(x0 xh y0 yl board[x][y]E){ dfs(board,x,y); } } }else{ board[i][j](char)(0count); } } }7. 衣橱整理题目链接LCR 130. 衣橱整理 - 力扣LeetCode题目描述如上图算法讲解FloodFill依旧是对m行n列的放个做一遍深度优先遍历即可代码实现class Solution { int ret; int h,l; boolean[][] vis; int[] dx{0,0,-1,1}; int[] dy{-1,1,0,0}; public int wardrobeFinishing(int m, int n, int t) { hm; ln; visnew boolean[h][l]; dfs(0,0,t); return ret; } public void dfs(int i,int j,int t){ vis[i][j]true; ret; for(int k0;k4;k){ int xidx[k]; int yjdy[k]; int tmp(x/10)(x%10)(y/10)(y%10); if(x0 xh y0 yl tmpt vis[x][y]false){ dfs(x,y,t); } } } }