LeetCode 题解工作台
飞地的数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、 1 表示一个陆地单元格。 一次 移动 是指从一个陆地单元格走到另一个相邻（ 上、下、左、右 ）的陆地单元格或跨过 grid 的边界。 返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。 示例 1：…
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以从边界上的陆地开始进行深度优先搜索，将所有与边界相连的陆地都标记为 。最后，统计剩余的 的个数，即为答案。 时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 和 分别为矩阵的行数和列数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] 输出：3 解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。
示例 2：
输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] 输出：0 解释：所有 1 都在边界上或可以到达边界。
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j]的值为0或1
解题思路
方法一：DFS
我们可以从边界上的陆地开始进行深度优先搜索，将所有与边界相连的陆地都标记为 。最后，统计剩余的 的个数，即为答案。
时间复杂度 ，空间复杂度 。其中 和 分别为矩阵的行数和列数。
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(i: int, j: int):
grid[i][j] = 0
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y]:
dfs(x, y)
m, n = len(grid), len(grid[0])
dirs = (-1, 0, 1, 0, -1)
for j in range(n):
for i in (0, m - 1):
if grid[i][j]:
dfs(i, j)
for i in range(m):
for j in (0, n - 1):
if grid[i][j]:
dfs(i, j)
return sum(sum(row) for row in grid)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate understands how to traverse the grid with DFS.
- question_mark
Candidate correctly identifies boundary-connected land cells.
- question_mark
Candidate shows ability to adapt grid problems to graph-based thinking.
常见陷阱
外企场景- error
Forgetting to mark boundary-connected cells, which can lead to incorrect counting of enclosed cells.
- error
Not handling edge cases such as very small grids or all sea cells.
- error
Confusing DFS/BFS traversal direction, leading to missed cells.
进阶变体
外企场景- arrow_right_alt
Adjusting the problem to check for different kinds of enclosed regions (e.g., with obstacles).
- arrow_right_alt
Handling 3D grid problems where cells can be connected in more than two dimensions.
- arrow_right_alt
Using BFS instead of DFS for exploring grid connections.