Medium

题目描述

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

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

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

示例 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.length
  • n == grid[i].length
  • 1 <= m, n <= 500
  • grid[i][j] 的值为 0 或 1

解题思路

这是一道典型的图遍历问题。关键思路是：能够走到边界的陆地单元格不是飞地，无法走到边界的陆地单元格才是飞地。

核心思路

我们可以采用"排除法"：

  1. 从所有边界上的陆地单元格开始，使用 DFS/BFS 遍历所有能够到达的陆地
  2. 将这些能够到达边界的陆地标记为已访问（或直接置为0）
  3. 最后统计剩余的陆地单元格数量，这些就是飞地

算法步骤

  1. 遍历矩阵的四条边界，对每个边界上值为1的单元格执行DFS
  2. DFS过程中将访问过的陆地标记（避免重复访问）
  3. 遍历完成后，统计矩阵中剩余的1的个数

其他解法思路

  • BFS方法：与DFS类似，从边界开始进行广度优先搜索
  • 并查集方法：将能连通边界的所有陆地归为一类，最后统计不属于这一类的陆地数量

推荐使用DFS方法，代码简洁且容易理解。

代码实现

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        function<void(int, int)> dfs = [&](int x, int y) {
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                return;
            }
            grid[x][y] = 0;
            dfs(x + 1, y);
            dfs(x - 1, y);
            dfs(x, y + 1);
            dfs(x, y - 1);
        };
        
        // 从边界开始DFS，标记所有能到达边界的陆地
        for (int i = 0; i < m; i++) {
            dfs(i, 0);      // 左边界
            dfs(i, n - 1);  // 右边界
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j);      // 上边界
            dfs(m - 1, j);  // 下边界
        }
        
        // 统计剩余的陆地数量
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] == 0:
                return
            grid[x][y] = 0
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        
        # 从边界开始DFS，标记所有能到达边界的陆地
        for i in range(m):
            dfs(i, 0)      # 左边界
            dfs(i, n - 1)  # 右边界
        
        for j in range(n):
            dfs(0, j)      # 上边界
            dfs(m - 1, j)  # 下边界
        
        # 统计剩余的陆地数量
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    count += 1
        
        return count

public class Solution {
    public int NumEnclaves(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        void Dfs(int x, int y) {
            if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0) {
                return;
            }
            grid[x][y] = 0;
            Dfs(x + 1, y);
            Dfs(x - 1, y);
            Dfs(x, y + 1);
            Dfs(x, y - 1);
        }
        
        // 从边界开始DFS，标记所有能到达边界的陆地
        for (int i = 0; i < m; i++) {
            Dfs(i, 0);      // 左边界
            Dfs(i, n - 1);  // 右边界
        }
        for (int j = 0; j < n; j++) {
            Dfs(0, j);      // 上边界
            Dfs(m - 1, j);  // 下边界
        }
        
        // 统计剩余的陆地数量
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var numEnclaves = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    const dfs = (x, y) => {
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)每个单元格最多被访问一次
空间复杂度O(m×n)DFS递归栈的最坏深度为矩阵大小