JZX轻语：简

LeetCode 1020 - 飞地的数量

发表于2024年06月04日

#BFS

该题目的本质就是求解和边界不相通的陆地单元格数量。可以使用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

题目链接：https://leetcode.cn/problems/number-of-enclaves/