What is a closed island in this problem?

A closed island is a group of 0s connected 4-directionally that is completely surrounded by 1s and does not touch the grid edges.

Should I use DFS or BFS for counting closed islands?

Either DFS or BFS works; DFS is simpler for recursive marking, while BFS uses a queue to avoid deep recursion issues.

How do I handle islands touching the grid border?

Perform an initial traversal of all border cells to mark any connected land as non-closed before counting islands internally.

What is the time complexity for this solution?

The solution runs in O(m \cdot n) time because every cell is visited at most twice, once for edge marking and once for counting.

Can this problem be solved using Union Find?

Yes, Union Find can merge connected land cells and track whether a component touches the border to identify closed islands efficiently.

#1254

Medium

auto_awesome图·搜索

LeetCode 题解工作台

统计封闭岛屿的数目

二维矩阵 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…

数组深度优先搜索广度优先搜索并查集矩阵

题目描述

二维矩阵 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

lightbulb

解题思路

方法一：DFS

遍历矩阵，对于每个陆地，我们进行深度优先搜索，找到与其相连的所有陆地，然后判断是否存在边界上的陆地，如果存在，则不是封闭岛屿，否则是封闭岛屿，答案加一。

最后返回答案即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int) -> int:
            res = int(0 < i < m - 1 and 0 < j < n - 1)
            grid[i][j] = 1
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y] == 0:
                    res &= dfs(x, y)
            return res

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        return sum(grid[i][j] == 0 and dfs(i, j) for i in range(m) for j in range(n))

speed

复杂度分析

指标	值
时间	complexity is O(m \cdot n) since every cell is visited at most twice (once during edge marking and once during island counting). Space complexity is O(m \cdot n) due to recursion stack or queue for DFS/BFS traversal of connected land cells.
空间	O(m \cdot n)

psychology

面试官常问的追问

外企场景

question_mark
Check if candidate correctly excludes border-connected land before counting islands.
question_mark
Watch for correct 4-directional connectivity handling in DFS or BFS.
question_mark
Confirm handling of varying grid sizes up to 100x100 without stack overflow.

warning

常见陷阱

外企场景

error
Counting islands that touch the grid edge as closed islands.
error
Using recursive DFS without considering maximum stack depth for large grids.
error
Failing to mark visited cells, leading to double counting of islands.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the size of the largest closed island instead of just the count.
arrow_right_alt
Allow diagonal connections when defining islands and adjust DFS/BFS accordingly.
arrow_right_alt
Use Union Find to dynamically merge land cells and detect closed islands.

help

常见问题

外企场景

继续练习

#1267 统计参与通信的服务器 #1391 检查网格中是否存在有效路径 #1020 飞地的数量