1254 Number of Closed Islands 统计封闭岛屿的数目

Description:

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:

Example 1:

[图片上传失败...(image-79b29b-1660570638242)]

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:

[图片上传失败...(image-881abc-1660570638242)]

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

题目描述：

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

请返回 封闭岛屿 的数目。

示例：

示例 1：

[图片上传失败...(image-1b281f-1660570638242)]

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

[图片上传失败...(image-4fb65f-1660570638242)]

输入：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
因为封闭岛屿需要完全被水域包围, 所以岛屿不能触碰边界
只要岛屿到达边界立即返回 false
如果岛屿碰到水域可以直接返回 true
需要将岛屿的 4 个方向都搜索一遍, 不能使用 && 运算符, 会短路
时间复杂度为 O(mn), 空间复杂度为 O(1)

代码:

C++:

class Solution 
{
private:
    bool dfs(int x, int y, vector<vector<int>>& grid, int m, int n)
    {
        if (x < 0 or x >= m or y < 0 or y >= n) return 0;
        if (grid[x][y]) return 1;
        grid[x][y] = 1;
        return dfs(x + 1, y, grid, m, n) & dfs(x, y + 1, grid, m, n) & dfs(x - 1, y, grid, m, n) & dfs(x, y - 1, grid, m, n);
    }
public:
    int closedIsland(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid.front().size(), result = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 0 and dfs(i, j, grid, m, n)) ++result; 
        return result;
    }
};

Java:

class Solution {
    public int closedIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length, result = 0;
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] == 0 && dfs(i, j, grid, m, n)) ++result; 
        return result;
    }
    
    private boolean dfs(int x, int y, int[][] grid, int m, int n) {
        if (x < 0 || x >= m || y < 0 || y >= n) return false;
        if (grid[x][y] == 1) return true;
        grid[x][y] = 1;
        return dfs(x + 1, y, grid, m, n) & dfs(x, y + 1, grid, m, n) & dfs(x - 1, y, grid, m, n) & dfs(x, y - 1, grid, m, n);
    }
}

Python:

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n, d = len(grid), len(grid[0]), [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        def dfs(x: int, y: int) -> int:
            if (not -1 < x < m) or (not -1 < y < n):
                return 0
            if grid[x][y]:
                return 1
            grid[x][y] = 1
            return reduce(and_, (dfs(x + dx, y + dy) for dx, dy in d))
        return sum(not grid[i][j] and dfs(i, j) for i in range(m) for j in range(n))