题目描述

有一个二维矩阵 grid，每个位置要么是陆地（记为 0）要么是水域（记为 1）。

我们从一块陆地出发，每次可以往上下左右 4 个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座 岛屿。

如果一座岛屿 完全 由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 封闭岛屿。

请返回封闭岛屿的数目。

样例

输入：
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 区域包围）。

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

输入：
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

算法1

(DFS) $O(mn)$

和LeetCode695有点类似，有两种解法，1.DFS，2.UnionFind。这题需要注意，边界grid外的点其实是海(1)。
1. 首先从是值是0的点开始dfs遍历，遍历过的点标记成-1。
2. dfs 4个方向，如果dfs到出了grid边界，把出边界的标记reachedBoundary变成true，表示本次陆地和边界外的点相连，不能算做一个封闭岛屿，res不能+1。否则res+1。
3. 继续循环找下一个没有遍历过的陆地，继续进行新的dfs搜索，并且重置reachedBoundary变成false，

Java 代码

public class Solution {
    int m = 0, n = 0, res = 0;
    int[] dx = new int[] {-1, 0, 1, 0};
    int[] dy = new int[] {0, 1, 0, -1};
    boolean reachedBoundary = false;

    public int closedIsland(int[][] grid) {
        m = grid.length;
        n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    reachedBoundary = false;
                    dfs(grid, i, j);
                    if (!reachedBoundary) {
                        res++;
                    }
                }
            }
        }

        return res;
    }

    private void dfs(int[][] grid, int row, int col) {
        if (row >= m || row < 0 || col >= n || col < 0) {
            reachedBoundary = true;
            return;
        }
        if (grid[row][col] != 0) {
            return;
        }
        grid[row][col] = -1;
        for (int i = 0; i < 4; i++) {
            int x = row + dx[i];
            int y = col + dy[i];
            dfs(grid, x, y);
        }
    }

}

算法2

(UnionFind) $O(mn)$

下次再写…(占位)

Java 代码

// todo