飞地的数量-LeetCode

1020. 飞地的数量 - Number of Enclaves

🎯 问题描述（来源于LeetCode）

描述：
给定一个 m x n 的二维网格 grid，其中 1 表示陆地，0 表示水域。
如果一个陆地格子无法通过上下左右移动到网格边界（即被水域包围），则称为“飞地”。
返回飞地的数量（即所有满足条件的陆地格子数）。

说明：

• 移动只能在四方向上。
• 边界上的陆地不算飞地（因为它们可以走到边界）。

示例：

• 示例 1：

输入: grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出: 3
解释: 有三个1被水包围，无法到达边界。

• 示例 2：

输入: grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出: 0
解释: 所有1都能到达边界。

💻 解题思路

思路：从边界 DFS 标记所有可达陆地，再统计剩余陆地

算法步骤

1. 获取网格尺寸 m, n。
2. 定义 DFS 函数 dfs(i, j)：
   • 如果坐标越界或当前格子不是陆地（grid[i][j] != 1），则返回。
   • 将当前格子标记为 0（表示已淹没）。
   • 向四个方向递归调用 dfs。
3. 从所有边界格子出发：
   • 遍历第一列和最后一列：如果 grid[i][0] == 1，则 dfs(i, 0)；如果 grid[i][n-1] == 1，则 dfs(i, n-1)。
   • 遍历第一行和最后一行：如果 grid[0][j] == 1，则 dfs(0, j)；如果 grid[m-1][j] == 1，则 dfs(m-1, j)。
   • 注意：四个角会被遍历两次，但不影响。
4. 经过上述操作，所有能到达边界的陆地都被标记为 0，剩下的 1 即为飞地。
5. 返回剩余 1 的总数：sum(sum(row) for row in grid)。

代码实现

from typing import List

class Solution:
    def numEnclaves(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] = 0
            for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
                dfs(i + di, j + dj)
        
        # 从边界开始淹没所有与边界相连的陆地
        for i in range(m):
            if grid[i][0] == 1:
                dfs(i, 0)
            if grid[i][n-1] == 1:
                dfs(i, n-1)
        for j in range(n):
            if grid[0][j] == 1:
                dfs(0, j)
            if grid[m-1][j] == 1:
                dfs(m-1, j)
        
        # 统计剩余 1 的数量（飞地）
        return sum(sum(row) for row in grid)

📊 性能分析

• 时间复杂度：$O(m \times n)$，每个格子最多被访问一次。
• 空间复杂度：$O(L)$，递归栈深度为连通区域大小，最坏 $O(m \times n)$。

思考

• 本题的核心是逆向思维：不直接找被包围的陆地，而是从边界陆地出发，淹没所有能到达边界的陆地，剩下的就是飞地。
• 也可以使用 BFS 替代 DFS，避免递归深度过大。
• 注意：题目要求返回飞地的数量，即剩余 1 的个数，而非布尔值。