发表于 2024.07.15

• 所谓的封闭是指四周全都被1包围的0，因此我们可以通过BFS遍历整个矩阵，将所有相邻的0视作为一个岛屿，如果四周没有遇到边界，说明就是封闭岛屿。为了避免重复遍历，我们可以将遍历过的0原地置为1，表示已经遍历过，且不会影响后续的遍历。

  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

• LC 题目链接