飞地的数量 图解题解

这道题到底在问什么

输入

grid 见右(5×5),靠边的陆地能走出去,中间一团走不出去

输出

3(中间那块 3 格陆地是飞地)

最优解：一步一步想明白

1. 3记住「从边界陆地往里 DFS 标记可达 → 剩下没标记的陆地就是飞地」,下面逐帧套它。
2. 4第一步,沿着最外面一圈走一遍。每碰到一个边界上的陆地,就从它钻进去,把所有能连通的陆地都标成「能走到边界」。
3. 5边界格 (0, 0) 是陆地(紫),说明这块陆地能走到边界。从它钻进去,把连着的陆地全标蓝(能出去)。
4. 6从 (0, 0) 看四周:往下、右也是陆地,把它们一并标成「能出去」(蓝)、继续往里走。
5. 7边界格 (0, 1) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
6. 8检查边界格 (0, 2):是海不是陆地,没什么可灌的,继续看下一个边界格。
7. 9检查边界格 (0, 3):是海不是陆地,没什么可灌的,继续看下一个边界格。
8. 10边界格 (0, 4) 是陆地(紫),说明这块陆地能走到边界。从它钻进去,把连着的陆地全标蓝(能出去)。
9. 11从 (0, 4) 看四周:往下也是陆地,把它们一并标成「能出去」(蓝)、继续往里走。
10. 12检查边界格 (4, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
11. 13检查边界格 (4, 1):是海不是陆地,没什么可灌的,继续看下一个边界格。
12. 14检查边界格 (4, 2):是海不是陆地,没什么可灌的,继续看下一个边界格。
13. 15检查边界格 (4, 3):是海不是陆地,没什么可灌的,继续看下一个边界格。
14. 16检查边界格 (4, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
15. 17边界格 (1, 0) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
16. 18检查边界格 (2, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
17. 19检查边界格 (3, 0):是海不是陆地,没什么可灌的,继续看下一个边界格。
18. 20边界格 (1, 4) 也是陆地,不过它刚才已经被同一片连通区灌到、标蓝了,不必再灌,看下一个。
19. 21检查边界格 (2, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
20. 22检查边界格 (3, 4):是海不是陆地,没什么可灌的,继续看下一个边界格。
21. 23四条边走完。左上角那块(含 (0,0)、(0,1)、(1,0))和右上角那块(含 (0,4)、(1,4))都从边界灌到了,全标蓝。海格(灰点)挡住了继续扩散,所以只有这两块靠边的连通陆地被灌到、标蓝;中间那团没被灌到。
22. 24倒灌结束。接下来把整张网格再扫一遍:凡是陆地、却没被标蓝的,就是怎么走都出不去的飞地,标绿、计数。
23. 25(2, 2) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 1。
24. 26(2, 3) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 2。
25. 27(3, 2) 是陆地,可它没被标蓝,说明从边界灌不到它、它也走不到边界,是飞地(绿)。飞地计数累加到 3。
26. 28整张网格扫完,绿色的飞地一共 3 格,这就是答案。回头看:从边界倒灌标记一遍 O(mn)、再扫一遍计数 O(mn),整体就是 O(mn)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def flood(sr: int, sc: int) -> None:
            # 显式栈迭代 DFS,避免大网格递归爆栈
            stack = [(sr, sc)]
            grid[sr][sc] = 0
            while stack:
                r, c = stack.pop()
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                        grid[nr][nc] = 0
                        stack.append((nr, nc))
        # 从四条边上的每个陆地倒灌
        for r in range(m):
            for c in (0, n - 1):
                if grid[r][c] == 1:
                    flood(r, c)
        for c in range(n):
            for r in (0, m - 1):
                if grid[r][c] == 1:
                    flood(r, c)
        return sum(sum(row) for row in grid)

#include <vector>
using namespace std;
class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        // 显式栈迭代 DFS,避免大网格递归爆栈
        auto flood = [&](int sr, int sc) {
            vector<pair<int,int>> stk{{sr, sc}};
            grid[sr][sc] = 0;
            while (!stk.empty()) {
                auto [r, c] = stk.back(); stk.pop_back();
                for (auto &d : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 0; stk.push_back({nr, nc});
                    }
                }
            }
        };
        for (int r = 0; r < m; ++r) for (int c : {0, n - 1})
            if (grid[r][c] == 1) flood(r, c);
        for (int c = 0; c < n; ++c) for (int r : {0, m - 1})
            if (grid[r][c] == 1) flood(r, c);
        int ans = 0;
        for (auto &row : grid) for (int x : row) ans += x;
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numEnclaves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int r = 0; r < m; r++) for (int c : new int[]{0, n - 1})
            if (grid[r][c] == 1) flood(grid, r, c, m, n, dirs);
        for (int c = 0; c < n; c++) for (int r : new int[]{0, m - 1})
            if (grid[r][c] == 1) flood(grid, r, c, m, n, dirs);
        int ans = 0;
        for (int[] row : grid) for (int x : row) ans += x;
        return ans;
    }
    // 显式栈迭代 DFS,避免大网格递归爆栈
    private void flood(int[][] grid, int sr, int sc, int m, int n, int[][] dirs) {
        Deque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[]{sr, sc});
        grid[sr][sc] = 0;
        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                    grid[nr][nc] = 0; stk.push(new int[]{nr, nc});
                }
            }
        }
    }
}

复杂度

面试官可能追问