1034. 边界着色 - Coloring A Border

🎯 问题描述（来源于LeetCode）

描述：
给定一个二维整数网格 grid，以及一个起始坐标 (row, col) 和一个新颜色 color。
将与起点四方向连通且颜色相同的所有格子组成的连通分量称为“连通分量”。
请将该连通分量的边界格子（即该格子至少有一个相邻格子（上下左右）不在同一连通分量内，或者位于网格边界）的颜色改为 color，并返回修改后的网格。

说明：

  • 连通分量中的内部格子（所有邻居都在同一连通分量内）保持原色不变。
  • 边界格子包括：网格边缘的格子，以及邻居中存在不同颜色或越界的格子。
  • 起始点 (row, col) 一定在网格内。

示例：

  • 示例 1：
1
2
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]]
解释: 整个网格都是相同颜色，边界上的格子被着色为2，内部中心格子保持1。
  • 示例 2：
1
2
输入: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出: [[1,3,3],[2,3,2]]

💻 解题思路

思路：DFS 标记连通分量 + 识别边界

算法步骤

  1. 初始化：

    • 获取网格尺寸 m, n。
    • 记录起点原始颜色 ori = grid[row][col]。
    • 创建 visited 二维数组，标记已访问格子。
    • 创建列表 borders，用于存储需要着色的边界格子坐标。

  2. 定义 DFS 函数 dfs(x, y)：

    • 标记 (x, y) 为已访问。
    • 初始化 is_border = False，表示当前格子是否为边界。
    • 遍历四个方向 (1,0), (-1,0), (0,1), (0,-1)：
      • 计算邻居坐标 (nx, ny)。
      • 如果邻居越界，或者邻居颜色不等于 ori，则说明当前格子是边界，设置 is_border = True。
      • 否则（邻居合法且颜色等于 ori），如果邻居未被访问，则递归调用 dfs(nx, ny)。
    • 如果 is_border 为 True，则将 (x, y) 加入 borders 列表。

  3. 启动 DFS：从起点 (row, col) 调用 dfs(row, col)。

  4. 着色：遍历 borders 列表，将每个格子的颜色改为 color。

  5. 返回修改后的 grid。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from typing import List

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])
        ori = grid[row][col]
        visited = [[False] * n for _ in range(m)]
        borders = []
        
        def dfs(x, y):
            visited[x][y] = True
            is_border = False
            for dx, dy in ((1,0), (-1,0), (0,1), (0,-1)):
                nx, ny = x + dx, y + dy
                if not (0 <= nx < m and 0 <= ny < n and grid[nx][ny] == ori):
                    is_border = True
                elif not visited[nx][ny]:
                    dfs(nx, ny)
            if is_border:
                borders.append((x, y))
        
        dfs(row, col)
        for x, y in borders:
            grid[x][y] = color
        return grid

📊 性能分析

  • 时间复杂度：O(m×n)O(m \times n)，每个格子最多访问一次。
  • 空间复杂度：O(m×n)O(m \times n)，visited 数组大小，加上递归栈深度（最坏为连通分量大小）。

思考

  • 本题关键是将“边界”定义为：在连通分量中，至少有一个相邻格子（四方向）要么越界，要么颜色与 ori 不同。
  • 注意：dfs 递归时，如果邻居颜色等于 ori 但已访问，则不再递归，避免重复。
  • 也可以使用 BFS 遍历，但 DFS 更简洁。
  • 特殊处理：如果起点本身颜色已经等于 color，但题目没有说明是否需要跳过，代码中仍会执行全部逻辑（着色边界，可能无变化），也可以提前判断 ori == color 直接返回，但并非必须。