DFS、BFS算法详解之岛屿问题

前言

岛屿问题是一个DFS应用的经典问题，主要的难点在于根据题目的应用语句构建出DFS中相应的剪枝与转移语句。再经过前面一篇文章DFS、BFS详解之二维矩阵路径问题的学习，我们应该能够推导出二维矩阵DFS遍历的两种框架：一种是纯DFS的上下左右遍历，一种是依赖于方向矩阵的上下左右遍历。

1、岛屿数量

我们一定要注意，在递归中一定要有结束条件，否则会陷入死循环，即使是没有返回值的函数，也要返回空，直接return;就完事。
我先给出一个错误的解法

class Solution {
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int count=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1')
                {
                    count++;
                    dfs(i,j,grid);
                }
            }
        }
        return count;
    }
    public void dfs(int i,int j,char [][]grid)
    {
        if(i>=0 && i<grid.length && j>=0 && j<grid[0].length)
        {
           if(grid[i][j] =='0') 
		     {
		     // 已经是海水了
		     return;
		     }
          grid[i][j]='0';
        }
        dfs(i+1,j,grid);
        dfs(i-1,j,grid);
        dfs(i,j+1,grid);
        dfs(i,j-1,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

上面的代码会导致栈溢出的错误，我们来分析一下为什么会导致栈的溢出，因为当i,j<0或者大于矩阵的长宽范围的时候，上面的代码是无法处理的，因为
他会始终进行递归而出不来，所以压入栈中的数据越来越多，最终导致爆栈。

class Solution {
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int count=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1')
                {
                    count++;
                    dfs(i,j,grid);
                }
            }
        }
        return count;
    }
    public void dfs(int i,int j,char [][]grid)
    {
        if(i>=0 && i<grid.length && j>=0 && j<grid[0].length)
        {
            grid[i][j]='0';
        }
        if(grid[i][j] =='0') 
        {
        // 已经是海水了
        return;
        }
        dfs(i+1,j,grid);
        dfs(i-1,j,grid);
        dfs(i,j+1,grid);
        dfs(i,j-1,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

这个代码的答案是错的，但不会引起栈溢出。首先来分析为什么不会引起栈溢出呢？因为题目中会有跳出递归的代码

if(grid[i][j] =='0') 
 {
 // 已经是海水了
 return;
 }
1
2
3
4
5

但是这个方案明显会导致答案的不对，因为在上面的代码

     if(i>=0 && i<grid.length && j>=0 && j<grid[0].length)
        {
            grid[i][j]='0';
        }
1
2
3
4

会将矩阵内满足条件的所有元素置为‘0’。从而使得dfs很快的就递归结束，count加的越来越多。

正确解法

class Solution {
    public int numIslands(char[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1')
                {
                    ans++;
                    dfs(i,j,m,n,grid);
                }
            }
        }
        return ans;
    }
    public void dfs(int i,int j,int m,int n,char[][]grid)
    {
        if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0')
        {
            return;
        }
        grid[i][j]='0';
        dfs(i+1,j,m,n,grid);
        dfs(i,j+1,m,n,grid);
        dfs(i-1,j,m,n,grid);
        dfs(i,j-1,m,n,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

这类 DFS 算法还有个别名叫做 FloodFill 算法。淹掉，QAQ。

2、统计封闭岛屿的数目

这道题经过上面一道题，应该说只要处理掉边缘的情况就好了。一开始我的想法是什么，在循环层，我就把外围给过滤掉，即从原来的：

for(int i=0;i<m;i++)
{
	for(int j=0;j<n;j++)
	{
		
	}
}
1
2
3
4
5
6
7

变为现在的

for(int i=1;i<m-1;i++)
{
	for(int j=1;j<n-1;j++)
	{
		
	}
}
1
2
3
4
5
6
7

但是我们忘记了各个数据点之间的粘性，看下面一个例子

我们可以看到在内部的两个零，其实是不能算作封闭的陆地的，因为通过外围的0，他还是与外部产生了联系。所以不能采用这种方法。
其实，我们之所以使用fs就应为dfs会让多个节点之间产生粘性，满足条件则继续，同时还能累计前面的信息，不满足条件则注解退出。

class Solution {
    public int closedIsland(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int j=0;j<n;j++)
        {
            dfs(0,j,m,n,grid);
            dfs(m-1,j,m,n,grid);
        }

        for(int i=0;i<m;i++)
        {
            dfs(i,0,m,n,grid);
            dfs(i,n-1,m,n,grid);
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==0)
                {
                    ans++;
                    dfs(i,j,m,n,grid);
                }
            }
        }
        return ans;
    }

    public void dfs(int i,int j,int m,int n,int[][] grid)
    {
        if(i<0 ||i>=m||j<0||j>=n||grid[i][j]==1)
        {
            return;
        }
        grid[i][j]=1;
        dfs(i+1,j,m,n,grid);
        dfs(i-1,j,m,n,grid);
        dfs(i,j-1,m,n,grid);
        dfs(i,j+1,m,n,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3、飞地的数量

class Solution {
    public int numEnclaves(int[][] grid) {
        //这一题不能斜着走，
        // 这一题我一开始的想法是判断内部的（就是不在边界上的）的节点的合法性
        //合法性函数判断其上下左右是否有陆地
        //后面发现此方法是不行的，可能它前后左右都有但是在外围一层全部断了，所以要有一个连续的状态去判断

       int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int j=0;j<n;j++)
        {
            dfs(0,j,m,n,grid);
            dfs(m-1,j,m,n,grid);
        }

        for(int i=0;i<m;i++)
        {
            dfs(i,0,m,n,grid);
            dfs(i,n-1,m,n,grid);
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                ans++;
                }
            }
        }
        return ans;
    }

    public void dfs(int i,int j,int m,int n,int[][] grid)
    {
        if(i<0 ||i>=m||j<0||j>=n||grid[i][j]==0)
        {
            return;
        }
        grid[i][j]=0;
        dfs(i+1,j,m,n,grid);
        dfs(i-1,j,m,n,grid);
        dfs(i,j-1,m,n,grid);
        dfs(i,j+1,m,n,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

4、岛屿的最大面积

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    ans=Math.max(ans,dfs(i,j,m,n,grid));
                }
            }
        }
        return ans;
    }
    public int dfs(int i,int j,int m,int n,int [][]grid)
    {
        if(i<0 || i>=m ||j<0 || j>=n||grid[i][j]==0)
        {
            return 0;
        }
        grid[i][j]=0;
        return 1+dfs(i+1,j,m,n,grid)+dfs(i-1,j,m,n,grid)+dfs(i,j+1,m,n,grid)+dfs(i,j-1,m,n,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

5、统计子岛屿

这道题一开始没有反应过来，没做出来。重点需要关注“子”+“岛屿”，子的意思是grid[2]中是"1"的位置(并且可能被我们判定为岛屿内的位置)grid[1]中必须与其相等也等于1,意思就是说grid1[i][j]=grid2[i][j]=1。但是这个条件还不够，为什么？
例如下面的情况：

红色的位置是不满足条件的，因为黑色的位置导致grid2中的岛屿形状很大（面积为3），在grid1中不能包围它，所以最终的数量不能增加。
分析到这里，我们的程序怎么写啊？其实还是不太好写，我们知道我们能通过 FloodFill算法算出grid2中有多少个岛屿，这是我们的第一题岛屿数量中的问题，我们使用了一个变量count来计数，只要grid2中的一个位置为1，则肯定有一个岛屿，不管这个岛屿多大（就一个方块还是拼起来是一个很大的图形）我们都无所谓，因为我们后续会将其淹掉。后面再判断grid2的位置上1的数量时，得到的都是独立的岛屿。但是现在不一样了，我们需要让count的值产生变化，随着dfs内部的比较信息产生变化。两者相等时，则不动，不等时，则置为0。同时淹掉整个岛屿（所有的粘性位置）,不受比较的影响。说到底，固定了一个量，从这个量中进行削减，而不是两个grid都动起来，这样很难做，条件会很乱。

class Solution {
    int count=1;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        int m=grid2.length;
        int n=grid2[0].length;
        int res=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid2[i][j]==1)
                {
                    count=1;
                    dfs(i,j,m,n,grid1,grid2);
                    res+=count;
                }
            }
        }
        return res; 
    }
    public void dfs(int i,int j,int m,int n,int [][]grid1,int [][]grid2)
    {
        if(i<0 || i>=grid2.length ||j<0 || j>=grid2[0].length || grid2[i][j]==0)
        {
            return;
        }
        if(grid1[i][j]==0)
        {
            count=0;
        }
        grid2[i][j]=0;
        dfs(i+1,j,m,n,grid1,grid2);
        dfs(i-1,j,m,n,grid1,grid2);
        dfs(i,j+1,m,n,grid1,grid2);
        dfs(i,j-1,m,n,grid1,grid2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

方法2，主动淹掉不满足条件的grid2中的岛屿。

class Solution {
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        //一定要拿住题目的包含的意思
        //并且岛屿是一个整体，会有连体的反应
        int count=0;
        int m=grid1.length;
        int n=grid1[0].length;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid2[i][j]==1 && grid1[i][j]==0)
                {
                    dfs(i,j,grid2);
                }
            }
        }
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid2[i][j]==1)
                {
                    count++;
                    dfs(i,j,grid2);
                }
            }
        }
        return count;

    }

    public void dfs(int i,int j,int [][]grid)
    {
        if(i<0 ||i>=grid.length ||j<0 ||j>=grid[0].length || grid[i][j]==0)
        {
            return;
        }
        grid[i][j]=0;
        dfs(i+1,j,grid);
        dfs(i-1,j,grid);
        dfs(i,j+1,grid);
        dfs(i,j-1,grid);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45