讨论/《广度优先搜索》 - 练习:边框着色/
《广度优先搜索》 - 练习:边框着色
共 3 个回复

读了半天题才明白是什么意思。。。

  • target = grid[r0][c0]
  • 查找(r0, c0)连通分量中,一个坐标的四周有不等于target的点,就染色该坐标

题解好多都是入队前检查,我比较习惯出队的检查,和之前的题对比需要一些改变

  • 出队校验周围的值是否等于target
  • 不能就地更改值,不然无法计算周围的情况
  • 可以记录符合要求的点,或用复制原矩阵(bfs 原矩阵, 根据坐标更改复制的矩阵的值,返回复制的矩阵)
def colorBorder(self, grid: List[List[int]], r0: int, c0: int, color: int) -> List[List[int]]:
        if not grid or not grid[0]: return grid
        m, n = len(grid), len(grid[0])
        # 目标值
        val = grid[r0][c0]
        # 方向
        directions = {(0, -1), (0, 1), (1, 0), (-1, 0)}
        # bfs 队列
        visited = {(r0, c0)}
        q = collections.deque(visited)
        # 符合要求的点
        change = set()

        while q:
            a, b = q.popleft()
            # 四周为目标值的点的个数,不为4说明该点为连通分量边界
            count = 0
            for _a, _b in directions:
                x, y = a + _a, b + _b
                # 周围的值为目标值,计数加一,如果没遍历过,入队
                if 0 <= x < m and 0 <= y < n and grid[x][y] == val:
                    count += 1
                    if (x, y) not in visited:
                        visited.add((x, y))
                        q.append((x, y))
            # (a, b) 点为边界点
            if count < 4:
                change.add((a, b))
        # 边界染色
        for i, j in change:
            grid[i][j] = color

        return grid
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