系统学习算法：专题十一floodfill算法

介绍：

floodfill算法简单来说就是求出相同性质的联通块

比如在上面这个矩阵中，如果我们要求出所有负数的联通块，就可以使用floodfill算法，但联通必须是上下左右，斜对角的不行

其中实现的方法有深度优先遍历（dfs）以及宽度优先遍历（bfs），这里主要使用的是dfs

跟之前走迷宫的方法大致一样，难度不大

题目一：

思路：

题意很简单，就是将[sr][sc]的这个值，从这一个点开始，将所有也等于这个值的联通块进行修改，修改成color这个值

这属于floodfill的其中一部分，这道题是只用修改包括起点的这一个联通块，而一般的是需要修改全部的联通块

 因为还是上下左右，所以先搞出方向向量数组，然后根据走迷宫类型的题dfs就行

只不过这里可以不用check记录数组，因为修改为color那么就不等于[sr][sc]了，就不会走重复的路了，当然前提要判断一下color和[sr][sc]不相同，如果相等就之间返回，不用修改了

当然也可以使用check记录数组，那么这样子就无所谓color和[sr][sc]相不相等

总体而言，还是不用check记录数组效率更高，空间节省了，时间也节省了

代码： class Solution { int row, col; // 方向向量数组 int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; // 值为num的要进行修改 int num; 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], y = j + dy[k]; //不越界&&值为num if (x >= 0 && x < row && y >= 0 && y < col && image[x][y] == num) { dfs(image, x, y, color); } } } public int[][] floodFill(int[][] image, int sr, int sc, int color) { // 如果相等就不用修改了 if (color == image[sr][sc]) { return image; } row = image.length; col = image[0].length; // 为num赋值 num = image[sr][sc]; dfs(image, sr, sc, color); return image; } } 题目二:

思路：

 题意很简单，就是求出所有为1的联通块的个数，上一道题是在一个联通块里进行修改，这道题就是找出所有联通块，然后数量加1

也是要有方向向量数组，然后用check来记录走过的陆地，上道题可用可不用，这里就需要用了，当然也可以不用，采用修改为‘0’作为标记，但不推荐，因为修改了原数据，如果要恢复也很麻烦

然后就去遍历数组，如果发现是一块新的岛屿，那么就从该起点开始，去标记所有该岛屿的陆地，最后标记完，结果加1，直到所有数组全部遍历之后，就返回结果

代码： class Solution { int ret, row, col; // 记录数组 boolean[][] check; // 方向向量数组 int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; public void dfs(char[][] grid, int i, int j) { // 修改标记 check[i][j] = true; // 上下左右 for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; // 如果没越界&&是陆地&&没走过 if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1' && check[x][y] == false) { dfs(grid, x, y); } } } public int numIslands(char[][] grid) { row = grid.length; col = grid[0].length; check = new boolean[row][col]; // 遍历数组 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { // 找到一块新岛屿 if (grid[i][j] == '1' && check[i][j] == false) { dfs(grid, i, j); ret++; } } } return ret; } } 题目三：

思路：

 和上一道题基本一样，只是求最大面积，那么我们按照之前思路，去找到每一个联通块，然后统计这一个联通块的面积，如果比现在的max还要大，就更新，否则就不更新

这里设计dfs可以有返回值也可以没有返回值，但思路都是一样的

代码1（有返回值）： class Solution { int ret, row, col; //记录数组 boolean[][] check; //方向向量数组 int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; public int dfs(int[][] grid, int i, int j) { //当前陆地面积 int sumall=1; //修改标记为走过了 check[i][j] = true; //上下左右 for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 1 && check[x][y] == false) { //加上这个方向的联通块面积 sumall+=dfs(grid, x, y); } } //返回包括该陆地的联通块面积 return sumall; } public int maxAreaOfIsland(int[][] grid) { row = grid.length; col = grid[0].length; check = new boolean[row][col]; //遍历数组 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { //如果是一块新的岛屿 if (grid[i][j] == 1 && check[i][j] == false) { //求出这块岛屿（联通块）的面积 int sum = dfs(grid, i, j); //选择最大的 if(sum>ret){ ret=sum; } } } } //返回最大面积 return ret; } } 代码2：（没有返回值）： class Solution { int ret, row, col; //记录数组 boolean[][] check; //方向向量数组 int[] dx = { 0, 0, 1, -1 }; int[] dy = { 1, -1, 0, 0 }; int sum; public void dfs(int[][] grid, int i, int j) { //当前陆地面积 sum++; //修改标记为走过了 check[i][j] = true; //上下左右 for (int k = 0; k < 4; k++) { int x = i + dx[k], y = j + dy[k]; if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 1 && check[x][y] == false) { //加上这个方向的联通块面积 dfs(grid, x, y); } } } public int maxAreaOfIsland(int[][] grid) { row = grid.length; col = grid[0].length; check = new boolean[row][col]; //遍历数组 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { //如果是一块新的岛屿 if (grid[i][j] == 1 && check[i][j] == false) { sum=0; //求出这块岛屿（联通块）的面积 dfs(grid, i, j); //选择最大的 if(sum>ret){ ret=sum; } } } } //返回最大面积 return ret; } } 题目四：

思路：

这道题思维要跳脱一下，不能跟着题目的要求来想，题目要求来捕获被围绕的区域，我们又怎么一开始知道是否是被围绕的区域，只能dfs到非法的位置时候才知道不是被围绕的区域，所以这时候就出现一开始不知道，所以没有进行修改，而之后知道了是不是，但又不好回溯了，就一根筋两头堵了

因此我们要改变为一开始就知道是否是被围绕的区域，所以采用正难则反的策略，题目要求找被围绕的区域，那么我们就先找没被围绕的区域，而这个区域一定在边界

所以我们只要找到所有边界的联通块，然后对其进行标记，比如修改为 ‘.’，然后再遍历整个数组，如果还是O，就说明是被围绕的区域，要修改为X，而是.的就说明不是围绕的区域，因此就恢复成O，最后就修改完成了

而这道题标记就可以采用修改的方式，因为本来就需要我们对原数据进行修改，不用采用标记数组

代码： class Solution { int row,col; //方向向量数组 int[] dx={0,0,1,-1}; int[] dy={1,-1,0,0}; //将所有边缘为O 的联通块修改为 . public void dfs(char[][] board,int i,int j){ //修改 board[i][j]='.'; //上下左右 for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; if(x>=0&&x<row&&y>=0&&y<col&&board[x][y]=='O'){ dfs(board,x,y); } } } public void solve(char[][] board) { row=board.length; col=board[0].length; //找第一行和最后一行的边界 for(int i=0;i<col;i++){ if(board[0][i]=='O'){ dfs(board,0,i); } if(board[row-1][i]=='O'){ dfs(board,row-1,i); } } //找中间行的左右边界 for(int i=1;i<row-1;i++){ if(board[i][0]=='O'){ dfs(board,i,0); } if(board[i][col-1]=='O'){ dfs(board,i,col-1); } } //遍历数组 for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ //如果是被围绕的区域 if(board[i][j]=='O'){ board[i][j]='X'; }else if(board[i][j]=='.'){//不是被围绕的区域 board[i][j]='O'; } } } } } 题目五：

思路：

题意比较难理解，但其实就是判断有哪些点的位置，能够从大到小流向太平洋和大西洋，将这些点全部返回

按照题目要求来想，就是遍历数组，如果从这个位置能到达行坐标-1或者列坐标-1，那么就能到达太平洋，而行列坐标能row/col，那么就能到达大西洋，对此分别进行标记，如果两个标记都有，说明符合题意，则添加，反之就不添加，但每次去dfs的时候，check标记数组都要重置

思路很简单，代码跟之前写的差不多

代码1（超时）： class Solution { int po,ao,row,col; //方向向量数组 int[] dx={0,0,1,-1}; int[] dy={1,-1,0,0}; //结果集 List<List<Integer>> ret=new ArrayList<>(); public void dfs(int[][] heights,int i,int j,boolean[][] check){ //上下左右 for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; //如果能到达太平洋 if(x==-1||y==-1){ //标记 po=1; }else if(x==row||y==col){//大西洋 ao=1; }else if(check[x][y]==false&&heights[x][y]<=heights[i][j]){//还没走到尽头 check[x][y]=true; dfs(heights,x,y,check); check[x][y]=false; } } } public List<List<Integer>> pacificAtlantic(int[][] heights) { row=heights.length; col=heights[0].length; //遍历数组 for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ //创建一个新的标记数组 boolean[][] check=new boolean[row][col]; dfs(heights,i,j,check); //如果这个位置能到达太平洋和大西洋 if(po==1&&ao==1){ List<Integer> list=new ArrayList<>(); list.add(i); list.add(j); //添加 ret.add(list); //恢复标记 po=0; ao=0; } } } return ret; } }

但是有很多重复了，明明之前深搜走过的路，又走一遍，因此效率很低，这道题也会超时

因此需要修改思路，还是正难则反，既然不确定这个位置是否能够到达太平洋和大西洋，那么就反过来从太平洋和大西洋开始，即边界开始，往上流回去，太平洋能流到的地方就标记太平洋，大西洋能流到的地方就标记大西洋，最后再遍历一遍数组，如果既有大西洋又有太平洋的标记，那么这个点就是可以的

这样避免了走许多重复的路

代码2： class Solution { int row,col; //标记数组 boolean[][] po,ao; //方向向量数组 int[] dx={0,0,1,-1}; int[] dy={1,-1,0,0}; //结果集 List<List<Integer>> ret=new ArrayList<>(); public void dfs(int[][] heights,int i,int j,boolean[][] check){ //在标记数组进行标记 check[i][j]=true; //上下左右 for(int k=0;k<4;k++){ int x=i+dx[k],y=j+dy[k]; //如果不越界&&没走过&&往高处流 if(x>=0&&x<row&&y>=0&&y<col&&check[x][y]==false&&heights[x][y]>=heights[i][j]){ dfs(heights,x,y,check); } } } public List<List<Integer>> pacificAtlantic(int[][] heights) { row=heights.length; col=heights[0].length; //太平洋标记数组 po=new boolean[row][col]; //大西洋标记数组 ao=new boolean[row][col]; //遍历上下边界 for(int j=0;j<col;j++){ dfs(heights,0,j,po); dfs(heights,row-1,j,ao); } //遍历左右边界 for(int i=0;i<row;i++){ dfs(heights,i,0,po); dfs(heights,i,col-1,ao); } //遍历数组 for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ //如果既有太平洋又有大西洋的标记 if(po[i][j]&&ao[i][j]){ List<Integer> list=new ArrayList<>(); list.add(i); list.add(j); //添加 ret.add(list); } } } return ret; } } 题目六：

思路：

题意比较难理解，简单来说就是给你一个棋盘，其中一开始只有M，E，然后会再告诉你一个坐标，这个坐标就是点击的意思，然后这时候就要返回点击之后棋盘的样子，空方格用B表示，周围有地雷，但这里有两种情况，一种是周围既有地雷又有空方格的，就返回个数，如果周围有地雷，但是没有空方格的，就不挖开，还是用E表示

如果运气背的，一开始就点到地雷，那么就将M改成X，剩下不变直接返回就好

其实这道题就是模拟的题，题目告诉你做法，只用实现就行，方法也告诉了用递归，也就是深搜（dfs），考察代码能力而已

这道题是八个方向的，所以方向向量数组要添加对角线方向，简单画一下x，y坐标变化情况，很容易知道dx：1，1，-1，-1分别对应dy：1，-1，1，-1

每深搜到一个格子就先遍历八个方向的格子，如果有地雷，就统计个数，并修改成对应个数，然后停止dfs，如果没有地雷，修改当前格子为B，继续深搜八个方向的

这样子，周围有空格子的一定会遍历到，而周围没有空格子的就还是为E

代码： class Solution { int row,col; //八个方向向量数组 int[] dx={0,0,1,-1,1,1,-1,-1}; int[] dy={1,-1,0,0,-1,1,-1,1}; public void dfs(char[][] board,int i,int j){ //周围雷的数量 int count=0; //八个方向去找雷 for(int k=0;k<8;k++){ int x=i+dx[k],y=j+dy[k]; //如果没越界&&有雷 if(x>=0&&x<row&&y>=0&&y<col&&board[x][y]=='M'){ //个数加1 count++; } } //如果周围有雷 if(count!=0){ //修改为雷的个数 board[i][j]=(char)(count+'0'); }else{//周围没雷 //修改为空格子 board[i][j]='B'; //继续深搜八个方向 for(int k=0;k<8;k++){ int x=i+dx[k],y=j+dy[k]; //如果没越界&&没找过的格子 if(x>=0&&x<row&&y>=0&&y<col&&board[x][y]=='E'){ dfs(board,x,y); } } } } public char[][] updateBoard(char[][] board, int[] click) { row=board.length; col=board[0].length; //如果开局点到雷 if(board[click[0]][click[1]]=='M'){ board[click[0]][click[1]]='X'; return board; } dfs(board,click[0],click[1]); return board; } } 题目七：

这一版的题目不容易看懂，如果看不懂的话可以看下面原版的题目

 

思路：

原版的题目给了操作步骤，所以要容易理解一些，就是从（0，0）开始，可以进行四个方向的移动，如果这个格子的x和y坐标的数位和（也就是每一位数的和）小于等于k，就能走，统计数加一，否则就不能走

而新版中虽然不好理解，但是也不是一无是处，新版提醒了只能向右和向下移动，为什么呢，因为向上和向左是之前走过的格子，数位之和一定小于k（因为向上的x坐标少1，向左的y坐标少1），因此接下来只有往数位更大的方向走，那就是向右和向下了（因为向下的x坐标多1，向右的y坐标多1）

那么求数位和就很简单，就是/10和%10这些操作，不多讲了

代码： class Solution { int row,col; //能走的格子个数 int count; //记录数组 boolean[][] check; public void dfs(int i,int j,int k){ //修改标记代表检查过了 check[i][j]=true; //数位和 int sum=0; //记录原来的i，j坐标 int bi=i; int bj=j; //求i的数位和 while(i!=0){ sum+=i%10; i/=10; } //求j的数位和 while(j!=0){ sum+=j%10; j/=10; } //如果数位和小于等于k if(sum<=k){ //这个格子能走 count++; //往右走&&没检查过 if(bj+1<col&&check[bi][bj+1]==false){ dfs(bi,bj+1,k); } //往下走&&没检查过 if(bi+1<row&&check[bi+1][bj]==false){ dfs(bi+1,bj,k); } } } public int wardrobeFinishing(int m, int n, int cnt) { row=m; col=n; check=new boolean[row][col]; //从（0，0）开始走 dfs(0,0,cnt); return count; } } 总结：

其实跟之前也没什么太大的区别，主要学到了一个正难则反的思想，其他还是老样子