LeetCode 1254 - 统计封闭岛屿的数目

from collections import deque


class Solution:
    moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

    def closedIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        def bfs(sr: int, sc: int) -> bool:
            """ 从一块陆地(sr, sc)开始BFS遍历该陆地所在岛屿，如果是封闭岛屿，返回True """
            nonlocal grid
            q = deque([(sr, sc)])
            grid[sr][sc] = 1
            is_island = True
            while q:
                r, c = q.popleft()
                for move in self.moves:
                    nr, nc = r + move[0], c + move[1]
                    if nr < 0 or nr >= m or nc < 0 or nc >= n:
                        # 遇到边界，不是封闭岛屿, 注意需要继续遍历完该岛屿, 只是该岛屿不能算封闭岛屿
                        is_island = False
                        continue
                    if grid[nr][nc] == 0:
                        # 遇到陆地，就地置为1，表示已经遍历过
                        grid[nr][nc] = 1
                        q.append((nr, nc))
            return is_island

        ans = 0
        for i in range(m):
            for j in range(n):
                if not grid[i][j]:
                    ans += bfs(i, j)
        return ans