LeetCode 1254. 统计封闭岛屿的数目

Categories:

题目描述
思路分析
1. 解法一：边界染色 + DFS 计数（推荐）
相似题目

题目描述

✅ 1254. 统计封闭岛屿的数目

思路分析

解法一：边界染色 + DFS 计数（推荐）

核心思路：

先从边界的 0 出发 DFS，将与边界相连的岛屿全部染成 1（非封闭）。

再遍历内部剩余的 0，每遇到一个岛屿就 DFS 染色并计数。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 表示网格行列数。

空间复杂度：O(mn)，递归栈最坏情况覆盖整个网格。

class Solution {
    private int m;
    private int n;

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

        // 先清除边界相连的岛屿
        for (int i = 0; i < m; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(grid, 0, j);
            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) {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 1) {
            return;
        }
        grid[x][y] = 1;
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}

func closedIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])

	var dfs func(x, y int)
	dfs = func(x, y int) {
		if x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 1 {
			return
		}
		grid[x][y] = 1
		dfs(x+1, y)
		dfs(x-1, y)
		dfs(x, y+1)
		dfs(x, y-1)
	}

	for i := 0; i < m; i++ {
		dfs(i, 0)
		dfs(i, n-1)
	}
	for j := 0; j < n; j++ {
		dfs(0, j)
		dfs(m-1, j)
	}

	count := 0
	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			if grid[i][j] == 0 {
				count++
				dfs(i, j)
			}
		}
	}
	return count
}

相似题目

题目	难度	考察点
1254. 统计封闭岛屿的数目	中等	DFS/BFS
200. 岛屿数量	中等	DFS/BFS
1020. 飞地的数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
130. 被围绕的区域	中等	DFS/BFS
463. 岛屿的周长	简单	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/79592558