介绍：
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;
}
}总结：
其实跟之前也没什么太大的区别，主要学到了一个正难则反的思想，其他还是老样子