LeetCode 题解工作台
边界着色
给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row 、 col 和 color 。网格中的每个值表示该位置处的网格块的颜色。 如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。 如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。 连通分量的边…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们从位置 $(row, col)$ 出发，利用 DFS 搜索所有颜色为 的网格块，如果该网格块的某个相邻位置的颜色不为 ，或者该网格块在网格的边界上，则将该网格块的颜色改为 。 时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。其中 和 分别是网格的行数和列数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
给你一个大小为 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.lengthn == grid[i].length1 <= m, n <= 501 <= grid[i][j], color <= 10000 <= row < m0 <= col < n
解题思路
方法一：DFS
我们从位置 出发，利用 DFS 搜索所有颜色为 的网格块，如果该网格块的某个相邻位置的颜色不为 ，或者该网格块在网格的边界上，则将该网格块的颜色改为 。
时间复杂度 ，空间复杂度 。其中 和 分别是网格的行数和列数。
class Solution:
def colorBorder(
self, grid: List[List[int]], row: int, col: int, color: int
) -> List[List[int]]:
def dfs(i: int, j: int, c: int) -> None:
vis[i][j] = True
for a, b in pairwise((-1, 0, 1, 0, -1)):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n:
if not vis[x][y]:
if grid[x][y] == c:
dfs(x, y, c)
else:
grid[i][j] = color
else:
grid[i][j] = color
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dfs(row, col, grid[row][col])
return grid
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n) in the worst case because every cell might be visited once. Space complexity is O(m_ n) due to the recursion stack in DFS or queue in BFS and storage of border cells. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focuses on DFS implementation details and border detection logic.
- question_mark
Checks handling of edge cases where the component touches the grid boundary.
- question_mark
May probe iterative vs recursive DFS/BFS trade-offs for array traversal.
常见陷阱
外企场景- error
Forgetting to check grid boundaries, which causes out-of-bounds errors.
- error
Incorrectly coloring interior cells instead of only borders.
- error
Revisiting cells without marking them, causing infinite recursion or excess work.
进阶变体
外企场景- arrow_right_alt
Coloring multiple disconnected components simultaneously with different target colors.
- arrow_right_alt
Allowing diagonal adjacency for connected components instead of only 4-directional.
- arrow_right_alt
Finding the smallest or largest border length after coloring without modifying the grid.