边界着色

标签: 深度优先搜索 广度优先搜索 数组 矩阵

难度: Medium

给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。

如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。

如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。

连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：

  • 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
  • 在网格的边界上（第一行/列或最后一行/列）

请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色。

并返回最终的网格 grid 。

示例 1：

输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出：[[3,3],[3,2]]

示例 2：

输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出：[[1,3,3],[2,3,3]]

示例 3：

输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
输出：[[2,2,2],[2,1,2],[2,2,2]]

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j], color <= 1000
  • 0 <= row < m
  • 0 <= col < n

Submission

运行时间: 26 ms

内存: 16.2 MB

from collections import deque

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        
        M, N = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        visited = set()
        
        grid_val = grid[row][col]
        
        queue = deque([(row, col)])
        visited.add((row, col))
        
        while queue:
            i, j = queue.popleft()
            is_border = False
            if i == 0 or i == M - 1 or j == 0 or j == N - 1:
                is_border = True
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if ni < 0 or nj < 0 or ni >= M or nj >= N:
                    continue
                if (ni, nj) in visited:
                    continue
                if grid[ni][nj] != grid_val:
                    is_border = True
                else:
                    queue.append((ni, nj))
                    visited.add((ni, nj))
            if is_border:
                grid[i][j] = color
        
        return grid

Explain

这个题解使用了广度优先搜索（BFS）来找出所有与起始网格块相连的网格块，并记录下是否位于边界或相邻于不同颜色的网格块。首先，初始化一个队列和一个访问集合，用于记录已访问的网格块。将起点加入队列和访问集合。然后，从队列中取出网格块，检查它是否位于边界，或者它的任一相邻网格块是否不属于同一连通分量（颜色不同或者已经越界）。如果满足这些条件，就将该网格块标记为边界，并将其颜色改为指定颜色。否则，如果相邻网格块属于同一连通分量且未被访问过，将其加入队列继续搜索。这个过程重复，直到队列为空，最后返回修改后的网格。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

from collections import deque

class Solution:
    def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
        
        M, N = len(grid), len(grid[0])  # 网格的长和宽
        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 上下左右四个方向
        visited = set()  # 访问记录
        
        grid_val = grid[row][col]  # 起始点颜色
        
        queue = deque([(row, col)])  # BFS队列初始化
        visited.add((row, col))  # 标记起始点为已访问
        
        while queue:
            i, j = queue.popleft()
            is_border = False  # 标记是否为边界
            if i == 0 or i == M - 1 or j == 0 or j == N - 1:  # 判断是否物理边界
                is_border = True
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if ni < 0 or nj < 0 or ni >= M or nj >= N:  # 越界检查
                    continue
                if (ni, nj) in visited:  # 已访问检查
                    continue
                if grid[ni][nj] != grid_val:  # 颜色不同，是边界
                    is_border = True
                else:
                    queue.append((ni, nj))  # 同色且未访问，加入队列继续探索
                    visited.add((ni, nj))
            if is_border:
                grid[i][j] = color  # 边界着色
        
        return grid

Explore

在广度优先搜索（BFS）中，队列用于维护待探索的节点顺序，确保算法按层次逐级处理节点，从而实现广度优先的搜索模式。访问集合则用于记录已经访问过的节点，防止重复处理同一个节点，这可以避免无限循环和不必要的计算重复。在处理图或网格这样的数据结构时，这种机制尤为重要，因为图中可能存在循环连接，而网格中网格块可能从多个方向被访问。

是的，这种判断方法确实会将接触到不同颜色网格块的内部网格块标记为边界。这是按照题目要求设计的，因为题目目的是着色所有位于边界的网格块，其中边界的定义包括物理边界和颜色边界。颜色边界指的是与其他颜色网格块接触的网格块，即使这些网格块位于内部。这样的设计确保了所有视觉上可以区分的边界都被标记和着色。

跳过已访问的网格块是为了避免重复处理和无限循环，这是BFS的常规操作。在本题解中，不会漏掉边界条件判断。因为一旦网格块被判断为边界并被着色，在整个BFS过程中，无论是从哪个方向访问，这个状态都不会改变。因此，即使跳过了已访问的网格块，判断边界的逻辑也已经在首次访问时完成了。

是的，算法的边界定义包括了所有可能的边界情况。物理边界包括网格的外围边缘，即最外层的行和列。此外，任何接触到不同颜色的网格块，即使是位于角落或内部但靠近物理边缘的网格块，都被视为边界。通过这种方式，算法确保所有视觉和逻辑上的边界都被考虑和处理。