讨论/《广度优先搜索》 - 练习:边框着色/
《广度优先搜索》 - 练习:边框着色
共 2 个回复
class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        m,n = len(grid),len(grid[0])
        que = collections.deque()
        visited = set()
        candidate = set()
        mycolor = grid[r0][c0]
        que.append((r0,c0))        
        visited.add((r0,c0))
        if self.is_boundry(r0,c0,m,n,grid):
            candidate.add((r0,c0))
        while que:
            level_len = len(que)
            for k in range(level_len):
                now = que.popleft()
                neighbors = self.find_neighbors(now[0],now[1],m,n)
                for xx in neighbors:
                    if grid[xx[0]][xx[1]] == mycolor and xx not in visited:
                        que.append(xx)
                        visited.add(xx)
                        if self.is_boundry(xx[0],xx[1],m,n,grid):
                            candidate.add(xx)
        for xx in candidate:
            grid[xx[0]][xx[1]] = color
        return grid

    def find_neighbors(self, i, j, m, n):
        neighbors = []
        if i-1 >= 0:
            neighbors.append((i-1,j))
        if i+1 <= m-1:
            neighbors.append((i+1,j))
        if j-1 >= 0:
            neighbors.append((i,j-1))
        if j+1 <= n-1:
            neighbors.append((i,j+1))
        return neighbors

    def is_boundry(self,i,j,m,n,grid):
        if i == 0 or i == m-1 or j == 0 or j == n-1:
            return True
        neighbors = self.find_neighbors(i,j,m,n)
        for xx in neighbors:
            if grid[xx[0]][xx[1]] != grid[i][j]:
                return True
        return False
class Solution:
    def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        row, col = len(grid), len(grid[0])
        visited = [[False for _ in range(col)] for _ in range(row)]
        pixels = self.bfs(grid, r0, c0, visited) # 返回所有在边界的像素点坐标
        while pixels:
            x, y = pixels.popleft()
            grid[x][y] = color
        return grid

    def bfs(self, grid, i, j, visited):
        row, col = len(grid), len(grid[0])
        pixels = collections.deque()
        que = collections.deque([(i, j)])
        visited[i][j] = True
        while que:
            curX, curY = que.popleft()
            if self.atBorder(grid, curX, curY, row, col):
                pixels.append((curX, curY))
            for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                x, y = curX + direction[0], curY + direction[1]
                if self.inArea(x, y, row, col) and not visited[x][y] and grid[x][y] == grid[curX][curY]:
                    que.append((x, y))
                    visited[x][y] = True 
        return pixels

    def inArea(self, x, y, row, col):
        return 0 <= x < row and 0 <= y < col 
    
    def atBorder(self, grid, x, y, row, col):
        if x == 0 or x == row-1 or y == 0 or y == col-1:
            return True 
        # 不在网格边界,肯定inArea
        for direction in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            i, j = x + direction[0], y + direction[1]
            if grid[i][j] != grid[x][y]:
                return True 
        return False