Medium

题目描述

给你一个大小为 m x n 的二进制网格 grid 。网格中 0 表示土地，1 表示水域。

岛屿是由四面连通的 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
  • 排除连接到边界的 0 组，因为它们不是封闭岛屿。
  • 返回网格中 0 的连通分量数目。

解题思路

这道题的核心思路是识别出真正"封闭"的岛屿。一个岛屿要成为封闭岛屿，必须完全被水域包围，不能触及网格边界。

解题思路分为两个关键步骤：

第一步：排除边界岛屿 首先遍历网格的四条边界，对于边界上所有值为 0 的位置，使用 DFS 或 BFS 将其所在的整个连通分量标记为已访问（可以修改为 1 或使用 visited 数组）。这样做的原因是：任何与边界相连的岛屿都不可能是封闭的，因为它们可以通过边界"逃逸"到网格外部。

第二步：计算剩余封闭岛屿 完成边界处理后，再次遍历整个网格的内部区域。每当遇到一个未访问的 0 时，说明发现了一个真正的封闭岛屿，使用 DFS 遍历整个岛屿并标记为已访问，同时将答案计数加 1。

这种方法巧妙地利用了"排除法"的思想：与其直接判断一个岛屿是否封闭（需要在遍历过程中检查是否触及边界），不如先排除所有不封闭的岛屿，剩下的自然就是封闭岛屿。

时间复杂度为 O(m×n)，因为每个格子最多被访问两次。空间复杂度为 O(m×n)，主要是递归调用栈的开销。

代码实现

class Solution {
public:
    int closedIsland(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 排除边界上的岛屿
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) dfs(grid, i, 0);
            if (grid[i][n-1] == 0) dfs(grid, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 0) dfs(grid, 0, j);
            if (grid[m-1][j] == 0) dfs(grid, m-1, j);
        }
        
        // 计算剩余的封闭岛屿
        int count = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j] == 0) {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 1) {
            return;
        }
        
        grid[i][j] = 1; // 标记为已访问
        dfs(grid, i+1, j);
        dfs(grid, i-1, j);
        dfs(grid, i, j+1);
        dfs(grid, i, j-1);
    }
};

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == 1:
                return
            
            grid[i][j] = 1  # 标记为已访问
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        
        # 排除边界上的岛屿
        for i in range(m):
            if grid[i][0] == 0:
                dfs(i, 0)
            if grid[i][n-1] == 0:
                dfs(i, n-1)
        
        for j in range(n):
            if grid[0][j] == 0:
                dfs(0, j)
            if grid[m-1][j] == 0:
                dfs(m-1, j)
        
        # 计算剩余的封闭岛屿
        count = 0
        for i in range(1, m-1):
            for j in range(1, n-1):
                if grid[i][j] == 0:
                    dfs(i, j)
                    count += 1
        
        return count

public class Solution {
    public int ClosedIsland(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 排除边界上的岛屿
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0) DFS(grid, i, 0);
            if (grid[i][n-1] == 0) DFS(grid, i, n-1);
        }
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 0) DFS(grid, 0, j);
            if (grid[m-1][j] == 0) DFS(grid, m-1, j);
        }
        
        // 计算剩余的封闭岛屿
        int count = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j] == 0) {
                    DFS(grid, i, j);
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private void DFS(int[][] grid, int i, int j) {
        if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length || grid[i][j] == 1) {
            return;
        }
        
        grid[i][j] = 1; // 标记为已访问
        DFS(grid, i+1, j);
        DFS(grid, i-1, j);
        DFS(grid, i, j+1);
        DFS(grid, i, j-1);
    }
}

var closedIsland = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    const dfs = (i, j) => {
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(m×n)需要遍历整个网格，每个格子最多被访问两次
空间复杂度O(m×n)递归调用栈的最大深度为网格大小