1020. 飞地的数量

exiaohu 于 2022-02-12 发布

题目链接:1020. 飞地的数量

grid 外围一圈陆地,然后从某个陆地开始,能够移动到的所有的陆地都不是飞地,否则就是飞地。

from collections import deque
from itertools import product
from typing import List


class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        m = len(grid)
        if m == 0:
            return 0

        n = len(grid[0])
        if n == 0:
            return 0

        grid = [[1] * (n + 2)] + [[1] + row + [1] for row in grid] + [[1] * (n + 2)]
        lands = set((i, j) for i, j in product(range(m + 2), range(n + 2)) if grid[i][j] == 1)
        points = deque([(0, 0)])

        def do(x, y):
            if (x, y) in lands:
                lands.remove((x, y))
                points.append((x, y))

        while points:
            i, j = points.popleft()
            do(i - 1, j)
            do(i + 1, j)
            do(i, j - 1)
            do(i, j + 1)
        return len(lands)