统计封闭岛屿的数目Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个完全由1包围（左、上、右、下）的岛。

请返回封闭岛屿的数目。

示例 1：

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2
解释：
灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。

示例 2：

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

示例 3：

输入：grid = [[1,1,1,1,1,1,1],
[1,0,0,0,0,0,1],
[1,0,1,1,1,0,1],
[1,0,1,0,1,0,1],
[1,0,1,1,1,0,1],
[1,0,0,0,0,0,1],
[1,1,1,1,1,1,1]]
输出：2

提示：

1 <= grid.length, grid[0].length <= 100
0 <= grid[i][j] <=1

# 思路

DFS

# 解法

class Solution {

    int m;
    int n;
    int[][] grid;
    int count = 0;
    public int closedIsland(int[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == 0) {
                    if(DFS(i,j)) count++;
                }
            }
        }
        return count;
    }

    private boolean DFS(int i,int j){
        if(i<0 || j<0 || i>=m || j>=n) return false;
        if(grid[i][j]==0){
            grid[i][j] = 1;
            boolean up = DFS(i-1,j);
            boolean down = DFS(i+1,j);
            boolean left = DFS(i,j-1);
            boolean right = DFS(i,j+1);
            return (up && down && left && right);
        }
        return true;    
    }
}

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

# 总结

分析出几种情况，然后分别对各个情况实现

#Java