题目链接: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)