LeetCode 1020. 飞地的数量

字数 3030 2025-12-22 20:15:15

LeetCode 1020. 飞地的数量

题目描述

给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格，1 表示一个陆地单元格。

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过网格的边界。我们定义“飞地”为无法在任意次数的移动中离开网格边界的陆地单元格的集合。

你的任务是返回网格中飞地的数量。简单来说，就是找出那些完全被海洋包围（即，不通过陆地连接到网格边界）的陆地单元格的数量。

示例解释

考虑一个网格：

grid = [
    [0,0,0,0],
    [1,0,1,0],
    [0,1,1,0],
    [0,0,0,0]
]

在这个网格中：

位于 (1,0) 的 1 是边界上的一个陆地（因为它位于第1行，行索引从0开始，所以行1是第二行，列0是第一列，这不算“边界”的定义）。等一下，让我们准确理解边界：矩阵的边界是指第一行、最后一行、第一列、最后一列。
检查边界上的单元格：
- 第一行 (0,0), (0,1), (0,2), (0,3) 都是0，没有陆地。
- 最后一行 (3,0), (3,1), (3,2), (3,3) 都是0，没有陆地。
- 第一列 (0,0), (1,0), (2,0), (3,0)：其中 (1,0) 是陆地 1，(2,0) 是0，(0,0) 是0，(3,0) 是0。所以 (1,0) 是一个边界陆地。
- 最后一列 (0,3), (1,3), (2,3), (3,3) 都是0，没有陆地。
从边界陆地 (1,0) 开始，它可以走到相邻的陆地。看看它能走到哪些陆地：
- 从 (1,0) 出发，可以向上、下、左、右走。上 (0,0) 是0，不行；下 (2,0) 是0，不行；左是边界外，不行；右 (1,1) 是0，不行。所以 (1,0) 自己就是一个孤立的边界陆地，但它能直接离开边界（因为它已经在边界上了，它自己就可以一步走出去）。根据定义，所有边界上的陆地本身，以及所有与边界陆地相连的内陆陆地，都不算飞地。因为从这些陆地，你都可以通过移动到达边界并离开网格。
再看其他陆地：
- (1,2) 是 1，它不是边界单元格（行1不是第一行也不是最后一行，列2不是第一列也不是最后一列）。检查它能否走到边界：它的邻居有上 (0,2)=0，下 (2,2)=1，左 (1,1)=0，右 (1,3)=0。从 (1,2) 可以走到 (2,2)。(2,2) 的邻居有上 (1,2)，下 (3,2)=0，左 (2,1)=1，右 (2,3)=0。从 (2,2) 可以走到 (2,1)。(2,1) 是陆地，它的邻居有上 (1,1)=0，下 (3,1)=0，左 (2,0)=0，右 (2,2)。所以，(1,2) 和 (2,2) 和 (2,1) 这三块陆地是连在一起的，但它们能走到边界吗？检查它们四个方向的所有邻居，没有一个单元格是在边界上（即行索引为0或m-1，或列索引为0或n-1）。所以，这三块陆地形成了一个“飞地”，因为它们被海洋包围，无法通过陆地路径走到边界。
所以，这个例子中，飞地是 (1,2), (2,1), (2,2) 这三个单元格，所以飞地的数量是3。

解题思路

这道题的本质是：找出所有那些不位于边界连通分量中的陆地单元格。
一个“连通分量”是指由相邻的（上、下、左、右）陆地单元格组成的一个区域。

解题过程可以分两步：

标记所有“非飞地”：从所有边界上的陆地单元格出发，进行深度优先搜索（DFS）或广度优先搜索（BFS），标记所有能访问到的陆地单元格。这些被标记的陆地单元格，因为它们与边界相连，所以它们不是飞地。
计数飞地：遍历整个网格，统计那些是陆地（值为1）但没有被上一步标记过的单元格。这些就是“飞地”，返回它们的数量。

另一种等价但更简洁的实现方式是：在第一步标记时，直接将这些“非飞地”陆地“淹没”成海洋（即，将值从1改为0）。然后在第二步，直接统计网格中剩余的陆地（值为1）的数量即可。

详细解题步骤

我们采用DFS方法，结合“淹没”非飞地的思路。

初始化：
- 获取网格的行数 m 和列数 n。
- 定义一个DFS递归函数 dfs(i, j)，其作用是从单元格 (i, j) 开始，将所有与之相连的陆地单元格“淹没”（设为0）。
淹没边界连通分量：
- 我们只关心从边界开始的陆地。所以，我们遍历网格的四条边：
  - 遍历第一行（i = 0）和最后一行（i = m-1）的所有列 j。
  - 遍历第一列（j = 0）和最后一列（j = n-1）的所有行 i。
- 对于边界上的每个单元格 (i, j)，如果它是陆地（grid[i][j] == 1），就调用 dfs(i, j)。这个DFS会把这块陆地以及所有与它相连的内陆陆地都变成海洋（0）。这样，所有能通过陆地路径走到边界的区域都被“清除”了。
DFS函数 dfs(i, j) 的具体实现：
- 递归终止条件：
  - 如果坐标 (i, j) 越界（i < 0 或 i >= m 或 j < 0 或 j >= n），则返回。
  - 如果当前单元格不是陆地（grid[i][j] == 0），则返回。
- 处理当前单元格：
  - 将当前陆地单元格“淹没”：grid[i][j] = 0。
- 递归探索四个方向：
  - 对当前单元格的上、下、左、右四个相邻位置，分别递归调用DFS函数：dfs(i-1, j), dfs(i+1, j), dfs(i, j-1), dfs(i, j+1)。
- 这样，DFS会像洪水一样，将所有连通的陆地都访问并淹没。
统计剩余陆地（飞地）：
- 经过第二步的淹没操作后，现在网格中剩下的所有值为 1 的陆地单元格，就是那些无法从边界到达的陆地，也就是“飞地”。
- 遍历整个网格的每一个单元格（使用两个嵌套的for循环，遍历所有行和列）。
- 如果 grid[i][j] == 1，则计数器 count 加1。
返回结果：
- 返回计数器 count 的值，即为飞地的数量。

为什么这个方法有效？

任何一块陆地，如果它是飞地，那么它一定不与任何边界陆地相连。因此，我们从边界陆地开始的DFS/BFS绝对不会访问到它。所以它在第一步不会被“淹没”，在第二步会被计数。
任何一块陆地，如果它不是飞地，那么它一定与某个边界陆地相连（通过一条陆地路径）。那么，在第一步中，当我们从那个边界陆地开始DFS时，就一定会访问并淹没它。所以它在第二步时已经变成了海洋（0），不会被计数。

思考扩展

这个问题可以看作是“岛屿数量”问题的一个变种。在标准的“岛屿数量”问题中，我们计算所有连通分量的个数。而在这里，我们只关心那些不接触边界的连通分量中的陆地单元格总数。
我们使用了DFS，你也可以使用BFS来实现第一步的标记/淹没过程，逻辑完全一样，只是将递归栈换成队列。
时间复杂度是 O(m * n)，因为每个单元格最多被访问一次（在DFS中）或两次（遍历边界和最后统计）。空间复杂度在最坏情况下（整个网格是陆地，递归深度）是 O(m * n)，但通常使用BFS可以优化为 O(min(m, n)) 的队列开销。

LeetCode 1020. 飞地的数量题目描述给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格， 1 表示一个陆地单元格。一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过网格的边界。我们定义“飞地”为无法在任意次数的移动中离开网格边界的陆地单元格的集合。你的任务是返回网格中飞地的数量。简单来说，就是找出那些完全被海洋包围（即，不通过陆地连接到网格边界）的陆地单元格的数量。示例解释考虑一个网格：在这个网格中：位于 (1,0) 的 1 是边界上的一个陆地（因为它位于第1行，行索引从0开始，所以行1是第二行，列0是第一列，这不算“边界”的定义）。等一下，让我们准确理解边界：矩阵的边界是指第一行、最后一行、第一列、最后一列。检查边界上的单元格：第一行 (0,0), (0,1), (0,2), (0,3) 都是0，没有陆地。最后一行 (3,0), (3,1), (3,2), (3,3) 都是0，没有陆地。第一列 (0,0), (1,0), (2,0), (3,0) ：其中 (1,0) 是陆地 1 ， (2,0) 是0， (0,0) 是0， (3,0) 是0。所以 (1,0) 是一个边界陆地。最后一列 (0,3), (1,3), (2,3), (3,3) 都是0，没有陆地。从边界陆地 (1,0) 开始，它可以走到相邻的陆地。看看它能走到哪些陆地：从 (1,0) 出发，可以向上、下、左、右走。上 (0,0) 是0，不行；下 (2,0) 是0，不行；左是边界外，不行；右 (1,1) 是0，不行。所以 (1,0) 自己就是一个孤立的边界陆地，但它能直接离开边界（因为它已经在边界上了，它自己就可以一步走出去）。根据定义，所有边界上的陆地本身，以及所有与边界陆地相连的内陆陆地，都不算飞地。因为从这些陆地，你都可以通过移动到达边界并离开网格。再看其他陆地： (1,2) 是 1 ，它不是边界单元格（行1不是第一行也不是最后一行，列2不是第一列也不是最后一列）。检查它能否走到边界：它的邻居有上 (0,2) =0，下 (2,2) =1，左 (1,1) =0，右 (1,3) =0。从 (1,2) 可以走到 (2,2) 。 (2,2) 的邻居有上 (1,2) ，下 (3,2) =0，左 (2,1) =1，右 (2,3) =0。从 (2,2) 可以走到 (2,1) 。 (2,1) 是陆地，它的邻居有上 (1,1) =0，下 (3,1) =0，左 (2,0) =0，右 (2,2) 。所以， (1,2) 和 (2,2) 和 (2,1) 这三块陆地是连在一起的，但它们能走到边界吗？检查它们四个方向的所有邻居，没有一个单元格是在边界上（即行索引为0或m-1，或列索引为0或n-1）。所以，这三块陆地形成了一个“飞地”，因为它们被海洋包围，无法通过陆地路径走到边界。所以，这个例子中，飞地是 (1,2) , (2,1) , (2,2) 这三个单元格，所以飞地的数量是3。解题思路这道题的本质是：找出所有那些不位于边界连通分量中的陆地单元格。一个“连通分量”是指由相邻的（上、下、左、右）陆地单元格组成的一个区域。解题过程可以分两步：标记所有“非飞地” ：从所有边界上的陆地单元格出发，进行深度优先搜索（DFS）或广度优先搜索（BFS），标记所有能访问到的陆地单元格。这些被标记的陆地单元格，因为它们与边界相连，所以它们不是飞地。计数飞地：遍历整个网格，统计那些是陆地（值为1）但没有被上一步标记过的单元格。这些就是“飞地”，返回它们的数量。另一种等价但更简洁的实现方式是：在第一步标记时，直接将这些“非飞地”陆地“淹没”成海洋（即，将值从1改为0）。然后在第二步，直接统计网格中剩余的陆地（值为1）的数量即可。详细解题步骤我们采用DFS方法，结合“淹没”非飞地的思路。初始化：获取网格的行数 m 和列数 n 。定义一个DFS递归函数 dfs(i, j) ，其作用是从单元格 (i, j) 开始，将所有与之相连的陆地单元格“淹没”（设为0）。淹没边界连通分量：我们只关心从边界开始的陆地。所以，我们遍历网格的四条边：遍历第一行（ i = 0 ）和最后一行（ i = m-1 ）的所有列 j 。遍历第一列（ j = 0 ）和最后一列（ j = n-1 ）的所有行 i 。对于边界上的每个单元格 (i, j) ，如果它是陆地（ grid[i][j] == 1 ），就调用 dfs(i, j) 。这个DFS会把这块陆地以及所有与它相连的内陆陆地都变成海洋（0）。这样，所有能通过陆地路径走到边界的区域都被“清除”了。 DFS函数 dfs(i, j) 的具体实现：递归终止条件：如果坐标 (i, j) 越界（ i < 0 或 i >= m 或 j < 0 或 j >= n ），则返回。如果当前单元格不是陆地（ grid[i][j] == 0 ），则返回。处理当前单元格：将当前陆地单元格“淹没”： grid[i][j] = 0 。递归探索四个方向：对当前单元格的上、下、左、右四个相邻位置，分别递归调用DFS函数： dfs(i-1, j) , dfs(i+1, j) , dfs(i, j-1) , dfs(i, j+1) 。这样，DFS会像洪水一样，将所有连通的陆地都访问并淹没。统计剩余陆地（飞地）：经过第二步的淹没操作后，现在网格中剩下的所有值为 1 的陆地单元格，就是那些无法从边界到达的陆地，也就是“飞地”。遍历整个网格的每一个单元格（使用两个嵌套的for循环，遍历所有行和列）。如果 grid[i][j] == 1 ，则计数器 count 加1。返回结果：返回计数器 count 的值，即为飞地的数量。为什么这个方法有效？任何一块陆地，如果它是飞地，那么它一定不与任何边界陆地相连。因此，我们从边界陆地开始的DFS/BFS 绝对不会访问到它。所以它在第一步不会被“淹没”，在第二步会被计数。任何一块陆地，如果它不是飞地，那么它一定与某个边界陆地相连（通过一条陆地路径）。那么，在第一步中，当我们从那个边界陆地开始DFS时，就一定会访问并淹没它。所以它在第二步时已经变成了海洋（0），不会被计数。思考扩展这个问题可以看作是“岛屿数量”问题的一个变种。在标准的“岛屿数量”问题中，我们计算所有连通分量的个数。而在这里，我们只关心那些不接触边界的连通分量中的陆地单元格总数。我们使用了DFS，你也可以使用BFS来实现第一步的标记/淹没过程，逻辑完全一样，只是将递归栈换成队列。时间复杂度是 O(m * n)，因为每个单元格最多被访问一次（在DFS中）或两次（遍历边界和最后统计）。空间复杂度在最坏情况下（整个网格是陆地，递归深度）是 O(m * n)，但通常使用BFS可以优化为 O(min(m, n)) 的队列开销。