发表于 2024.06.04

• 该题目的本质就是求解和边界不相通的陆地单元格数量。可以使用BFS就地对和边界相连的陆地单元格进行标记(将其改为2即可)，然后再次遍历整个矩阵，统计未被标记的陆地单元格数量。

  这里有两个注意点：

  1. 避免重复标记，可以在遍历边界时，避免重复标记。

  2. 在移动的时候就标记为2，而非在出队的时候标记，避免重复入队浪费时间。

  class Solution:
      moves = (
          (-1, 0),
          (1, 0),
          (0, -1),
          (0, 1)
      )
  
      def numEnclaves(self, grid: List[List[int]]) -> int:
          m, n = len(grid), len(grid[0])
          # 通过bfs将和边界相邻的1进行标记
          q = deque()
          for i in range(n):
              if grid[0][i] == 1:
                  grid[0][i] = 2
                  q.append((0, i))
              
              # 注意点: 避免重复标记
              if m > 1 and grid[m - 1][i] == 1:
                  grid[m - 1][i] = 2
                  q.append((m - 1, i))
          for i in range(m):
              if grid[i][0] == 1:
                  grid[i][0] = 2
                  q.append((i, 0))
              if n > 1 and grid[i][n - 1] == 1:
                  grid[i][n - 1] = 2
                  q.append((i, n - 1))
  
          while q:
              r, c = q.popleft()
              for move in self.moves:
                  nr, nc = r + move[0], c + move[1]
                  if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                      q.append((nr, nc))
                      # 注意点2: 在移动的时候就标记, 而非在出队的时候标记, 避免重复入队
                      grid[nr][nc] = 2
  
          ans = 0
          for row in grid:
              for item in row:
                  ans += (item == 1)
          return ans

• LC 题目链接