讨论/《广度优先搜索》 - 练习:飞地的数量/
《广度优先搜索》 - 练习:飞地的数量
共 1 个回复
class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        row, col = len(grid), len(grid[0])
        que = collections.deque()
        for i in range(row):
            for j in range(col):
                if i == 0 or i == row - 1 or j == 0 or j == col - 1:
                    if grid[i][j] == 1:
                        que.append((i, j))
                        grid[i][j] = 2
        
        self.bfs(grid, que)
        
        ans = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == 1:
                    ans += 1
        return ans 

    def bfs(self, grid, que):
        row, col = len(grid), len(grid[0])
        while que:
            curX, curY = que.popleft()
            for directions in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                x, y = curX + directions[0], curY + directions[1]
                if self.inArea(x, y, row, col) and grid[x][y] == 1:
                    que.append((x, y))
                    grid[x][y] = 2
    
    def inArea(self, x, y, row, col):
        return 0 <= x < row and 0 <= y < col