LeetCode 1020. 飞地的数量

字数 2351 2025-11-04 11:59:17

LeetCode 1020. 飞地的数量

题目描述

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

一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

请你返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。

简单来说，就是找出所有完全被海洋（或边界）包围的、"封闭"的陆地单元格的数量。这些陆地单元格无法通过上下左右的移动走到网格的边界之外。

解题过程

这个问题本质上是要找出所有不与边界相连的陆地连通块。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来标记所有能从边界到达的陆地。那么，剩下的、未被标记的陆地，就是题目要求的"飞地"。

循序渐进讲解

核心思路分析
题目要求的是"无法离开网格边界的陆地单元格"。反过来想，什么样的陆地是"可以离开边界"的呢？就是从这块陆地出发，通过上下左右移动，最终能走到网格的边界上。
那么，如果我们能从网格的四条边界上的所有陆地单元格出发，进行搜索（DFS/BFS），把所有能到达的陆地都做一个"已访问"的标记。那么，最终网格中所有没有被标记的、值为1的单元格，就是那些无法到达边界的"飞地"。
算法选择
这是一个典型的连通性问题，我们使用深度优先搜索（DFS） 来解决。DFS 非常适合遍历一个连通区域，我们会递归地访问当前单元格的所有相邻陆地单元格。
详细步骤
- 步骤一：初始化
  获取网格的行数 m 和列数 n。
  我们不需要额外的数据结构来记录"飞地"，但需要一个和 grid 同样大小的二维数组 visited，用来记录某个单元格是否已经被访问过（即是否是从边界可达的）。初始化时所有值都为 false（未访问）。
- 步骤二：搜索边界上的陆地
  我们只关心从边界陆地出发能到达哪些地方。因此，我们遍历网格的四条边：
  - 上边界和下边界：遍历每一列（col 从 0 到 n-1）。
    - 检查上边界第一行（row = 0）的单元格。如果它是陆地（grid[0][col] == 1）且未被访问过，就从 (0, col) 开始进行 DFS。
    - 检查下边界最后一行（row = m-1）的单元格。如果它是陆地（grid[m-1][col] == 1）且未被访问过，就从 (m-1, col) 开始进行 DFS。
  - 左边界和右边界：遍历每一行（row 从 0 到 m-1）。
    - 检查左边界第一列（col = 0）的单元格。如果它是陆地（grid[row][0] == 1）且未被访问过，就从 (row, 0) 开始进行 DFS。
    - 检查右边界最后一列（col = n-1）的单元格。如果它是陆地（grid[row][n-1] == 1）且未被访问过，就从 (row, n-1) 开始进行 DFS。
- 步骤三：实现深度优先搜索（DFS）函数
  这个 DFS 函数 dfs(row, col, grid, visited) 的目的是标记所有与 (row, col) 连通的陆地单元格为已访问。
  - 参数：当前单元格的行 row、列 col，网格 grid，访问标记数组 visited。
  - 递归终止条件：
    1. 当前坐标 (row, col) 越界（row < 0 或 row >= m 或 col < 0 或 col >= n）。
    2. 当前单元格是海洋（grid[row][col] == 0）。
    3. 当前单元格已经被访问过（visited[row][col] == true）。
      如果满足以上任何一条，直接返回。
  - 处理当前单元格：
    将 visited[row][col] 标记为 true。
  - 递归探索四个方向：
    对当前单元格的四个相邻方向（上、下、左、右）分别进行 DFS。
    - 上方：dfs(row - 1, col, grid, visited)
    - 下方：dfs(row + 1, col, grid, visited)
    - 左方：dfs(row, col - 1, grid, visited)
    - 右方：dfs(row, col + 1, grid, visited)
- 步骤四：统计飞地数量
  在完成了步骤二（从所有边界陆地出发进行DFS）之后，整个网格中所有能从边界到达的陆地都已经被标记在 visited 数组中了。
  现在，我们遍历网格中的每一个单元格（使用两层循环）：
  - 如果这个单元格是陆地（grid[row][col] == 1）并且没有被访问过（visited[row][col] == false），那么它就是一个"飞地"。
    统计满足上述条件的单元格的数量，这个数量就是最终的答案。
复杂度分析
- 时间复杂度：O(m * n)。我们需要遍历网格的边界（大约是 O(m+n)）来启动 DFS，而每个单元格在 DFS 中最多被访问一次。后续统计飞地数量也需要遍历整个网格（O(m*n)）。因此总时间复杂度是线性的，与网格大小成正比。
- 空间复杂度：O(m * n)。空间消耗主要来自 DFS 的递归调用栈和 visited 数组。在最坏情况下（整个网格都是陆地），递归深度可能达到 O(mn)。visited 数组也占用 O(mn) 的空间。

总结
解决这个问题的关键是转换视角：不去直接寻找封闭的陆地，而是先找出所有"不封闭"（与边界连通）的陆地并标记它们。剩下的陆地自然就是封闭的飞地。DFS 是解决这种连通性标记问题的有力工具。

LeetCode 1020. 飞地的数量题目描述给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格， 1 表示一个陆地单元格。一次移动是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。请你返回网格中无法在任意次数的移动中离开网格边界的陆地单元格的数量。简单来说，就是找出所有完全被海洋（或边界）包围的、"封闭"的陆地单元格的数量。这些陆地单元格无法通过上下左右的移动走到网格的边界之外。解题过程这个问题本质上是要找出所有不与边界相连的陆地连通块。我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来标记所有能从边界到达的陆地。那么，剩下的、未被标记的陆地，就是题目要求的"飞地"。循序渐进讲解核心思路分析题目要求的是"无法离开网格边界的陆地单元格"。反过来想，什么样的陆地是"可以离开边界"的呢？就是从这块陆地出发，通过上下左右移动，最终能走到网格的边界上。那么，如果我们能从网格的四条边界上的所有陆地单元格出发，进行搜索（DFS/BFS），把所有能到达的陆地都做一个"已访问"的标记。那么，最终网格中所有没有被标记的、值为1的单元格，就是那些无法到达边界的"飞地"。算法选择这是一个典型的连通性问题，我们使用深度优先搜索（DFS）来解决。DFS 非常适合遍历一个连通区域，我们会递归地访问当前单元格的所有相邻陆地单元格。详细步骤步骤一：初始化获取网格的行数 m 和列数 n 。我们不需要额外的数据结构来记录"飞地"，但需要一个和 grid 同样大小的二维数组 visited ，用来记录某个单元格是否已经被访问过（即是否是从边界可达的）。初始化时所有值都为 false （未访问）。步骤二：搜索边界上的陆地我们只关心从边界陆地出发能到达哪些地方。因此，我们遍历网格的四条边：上边界和下边界：遍历每一列（ col 从 0 到 n-1 ）。检查上边界第一行（ row = 0 ）的单元格。如果它是陆地（ grid[0][col] == 1 ）且未被访问过，就从 (0, col) 开始进行 DFS。检查下边界最后一行（ row = m-1 ）的单元格。如果它是陆地（ grid[m-1][col] == 1 ）且未被访问过，就从 (m-1, col) 开始进行 DFS。左边界和右边界：遍历每一行（ row 从 0 到 m-1 ）。检查左边界第一列（ col = 0 ）的单元格。如果它是陆地（ grid[row][0] == 1 ）且未被访问过，就从 (row, 0) 开始进行 DFS。检查右边界最后一列（ col = n-1 ）的单元格。如果它是陆地（ grid[row][n-1] == 1 ）且未被访问过，就从 (row, n-1) 开始进行 DFS。步骤三：实现深度优先搜索（DFS）函数这个 DFS 函数 dfs(row, col, grid, visited) 的目的是标记所有与 (row, col) 连通的陆地单元格为已访问。参数：当前单元格的行 row 、列 col ，网格 grid ，访问标记数组 visited 。递归终止条件：当前坐标 (row, col) 越界（ row < 0 或 row >= m 或 col < 0 或 col >= n ）。当前单元格是海洋（ grid[row][col] == 0 ）。当前单元格已经被访问过（ visited[row][col] == true ）。如果满足以上任何一条，直接返回。处理当前单元格：将 visited[row][col] 标记为 true 。递归探索四个方向：对当前单元格的四个相邻方向（上、下、左、右）分别进行 DFS。上方： dfs(row - 1, col, grid, visited) 下方： dfs(row + 1, col, grid, visited) 左方： dfs(row, col - 1, grid, visited) 右方： dfs(row, col + 1, grid, visited) 步骤四：统计飞地数量在完成了步骤二（从所有边界陆地出发进行DFS）之后，整个网格中所有能从边界到达的陆地都已经被标记在 visited 数组中了。现在，我们遍历网格中的每一个单元格（使用两层循环）：如果这个单元格是陆地（ grid[row][col] == 1 ）并且没有被访问过（ visited[row][col] == false ），那么它就是一个"飞地"。统计满足上述条件的单元格的数量，这个数量就是最终的答案。复杂度分析时间复杂度：O(m * n) 。我们需要遍历网格的边界（大约是 O(m+n)）来启动 DFS，而每个单元格在 DFS 中最多被访问一次。后续统计飞地数量也需要遍历整个网格（O(m* n)）。因此总时间复杂度是线性的，与网格大小成正比。空间复杂度：O(m * n) 。空间消耗主要来自 DFS 的递归调用栈和 visited 数组。在最坏情况下（整个网格都是陆地），递归深度可能达到 O(m n)。 visited 数组也占用 O(m n) 的空间。总结解决这个问题的关键是转换视角：不去直接寻找封闭的陆地，而是先找出所有"不封闭"（与边界连通）的陆地并标记它们。剩下的陆地自然就是封闭的飞地。DFS 是解决这种连通性标记问题的有力工具。