1254. Number of Closed Islands (M)

https://leetcode.com/problems/number-of-closed-islands/

Given a 2D grid consists of 0s (land) and 1s (water). An island is a maximal 4-directionally connected group of 0s and a closed island is an island totally (all left, top, right, bottom) surrounded by 1s.

Return the number of closed islands.

Example 1:

Input: 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]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 1

Example 3:

Input: 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]]
Output: 2

Constraints:

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

Solution:

Version 1: DFS

那么如何判断「封闭岛屿」呢？其实很简单，把LeetCode 200 中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？

有了这个思路，就可以直接看代码了，注意这题规定 0 表示陆地，用 1 表示海水：

// 主函数：计算封闭岛屿的数量
int closedIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int j = 0; j < n; j++) {
        // 把靠上边的岛屿淹掉
        dfs(grid, 0, j);
        // 把靠下边的岛屿淹掉
        dfs(grid, m - 1, j);
    }
    for (int i = 0; i < m; i++) {
        // 把靠左边的岛屿淹掉
        dfs(grid, i, 0);
        // 把靠右边的岛屿淹掉
        dfs(grid, i, n - 1);
    }
    // 遍历 grid，剩下的岛屿都是封闭岛屿
    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0) {
                res++;
                dfs(grid, i, j);
            }
        }
    }
    return res;
}

// 从 (i, j) 开始，将与之相邻的陆地都变成海水
void dfs(int[][] grid, int i, int j) {
    int m = grid.length, n = grid[0].length;
    if (i < 0 || j < 0 || i >= m || j >= n) {
        return;
    }
    if (grid[i][j] == 1) {
        // 已经是海水了
        return;
    }
    // 将 (i, j) 变成海水
    grid[i][j] = 1;
    // 淹没上下左右的陆地
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}

只要提前把靠边的陆地都淹掉，然后算出来的就是封闭岛屿了。

Version 2: Union Find

Previous200.Number of Islands (M)Next1020. Number of Enclaves (M)

Last updated 3 years ago

Was this helpful?

Input: 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]] Output: 2 Explanation: Islands in gray are closed because they are completely surrounded by water (group of 1s).

Input: 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]] Output: 2

// 主函数：计算封闭岛屿的数量 int closedIsland(int[][] grid) { int m = grid.length, n = grid[0].length; for (int j = 0; j < n; j++) { // 把靠上边的岛屿淹掉 dfs(grid, 0, j); // 把靠下边的岛屿淹掉 dfs(grid, m - 1, j); } for (int i = 0; i < m; i++) { // 把靠左边的岛屿淹掉 dfs(grid, i, 0); // 把靠右边的岛屿淹掉 dfs(grid, i, n - 1); } // 遍历 grid，剩下的岛屿都是封闭岛屿 int res = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { res++; dfs(grid, i, j); } } } return res; } // 从 (i, j) 开始，将与之相邻的陆地都变成海水 void dfs(int[][] grid, int i, int j) { int m = grid.length, n = grid[0].length; if (i < 0 || j < 0 || i >= m || j >= n) { return; } if (grid[i][j] == 1) { // 已经是海水了 return; } // 将 (i, j) 变成海水 grid[i][j] = 1; // 淹没上下左右的陆地 dfs(grid, i + 1, j); dfs(grid, i, j + 1); dfs(grid, i - 1, j); dfs(grid, i, j - 1); }