LeetCode 1034. 边界着色
字数 2981 2025-12-07 09:54:29

LeetCode 1034. 边界着色

题目描述

给定一个大小为 m x n 的二维整数矩阵 grid，表示一个网格。再给定一个整数 row, col 和一个整数 color。矩阵中的每个值表示该位置像素的颜色。

“连通分量”定义为：从某个起始像素（坐标 (row, col)）开始，所有与该像素颜色相同，并且通过水平或垂直方向（上、下、左、右）相邻连接的像素构成的区域。

“边界”是指连通分量中，满足以下任一条件的像素：

  1. 该像素位于整个网格的边界上（即行号为 0 或 m-1，或列号为 0 或 n-1）。
  2. 该像素在连通分量内部，但它的上、下、左、右四个相邻像素中，至少有一个像素的颜色与连通分量的颜色不同。

你的任务是：找到包含起始像素 (row, col) 的连通分量，并将这个连通分量中的所有边界像素的颜色，更改为 color。

最终，你需要返回修改后的矩阵。

示例 1:
输入: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
输出: [[3,3],[3,2]]
解释: 起始像素颜色为1，连通分量是 (0,0), (0,1), (1,0)。这个分量的边界是 (0,0), (0,1), (1,0)，因为它们要么在网格边界上，要么有邻居颜色不是1。将边界改为3。中心(1,1)颜色是2，不属于此分量，不变。

示例 2:
输入: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
输出: [[1,3,3],[2,3,3]]
解释: 起始像素颜色为2。连通分量是 (0,1), (0,2), (1,2)。边界像素是 (0,1)（邻居(0,0)颜色为1，不同）和 (0,2), (1,2)（在网格边界上）。内部的(1,1)颜色为3，不属此分量。(1,0)颜色为2，但不与 (0,1) 四连通。

解题过程循序渐进讲解

步骤 1: 理解核心任务
题目核心是“查找连通分量”和“判断边界”。我们需要：

  1. 搜索：从 (row, col) 出发，找出所有颜色为 original_color = grid[row][col] 且与其四连通的像素坐标。这是一个“洪水填充”问题。
  2. 标记边界：在搜索过程中，对于遇到的每一个属于该连通分量的像素，判断它是否属于“边界”。
  3. 着色：将所有被标记为边界的像素，其颜色改为目标 color。

步骤 2: 选择搜索算法
我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）。两者皆可，这里以 BFS 为例进行说明，因为它更直观，且无需担心递归深度问题。

  • 使用一个队列 queue 来存储待访问的单元格坐标。
  • 使用一个集合 visited 或一个与网格同大小的布尔数组，来记录已访问过的单元格，避免重复访问和死循环。

步骤 3: 详细设计 BFS 过程

  1. 初始化：

    • 获取原始颜色 original_color = grid[row][col]。如果 original_color 已经等于目标 color，根据题意，可以直接返回原矩阵（避免不必要的修改和循环）。
    • 初始化队列 queue，将起始坐标 (row, col) 加入队列。
    • 初始化访问标记（例如 m x n 的布尔矩阵 visited），将起始点标记为已访问。
    • 初始化一个列表 borders 用于存储所有边界像素的坐标。

  2. 方向数组：定义 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] 表示四个移动方向。

  3. BFS 循环（当队列不为空时）：
    a. 从队列中取出一个坐标 (r, c)。
    b. 关键：判断当前 (r, c) 是否为边界。
    - 条件1：如果 r == 0 或 r == m-1 或 c == 0 或 c == n-1，那么它在网格边界上，是边界。
    - 条件2：检查其四个邻居。遍历 directions，计算邻居坐标 (nr, nc)。如果邻居坐标不合法（越界）或者合法但其颜色不等于 original_color，那么说明当前像素 (r, c) 至少有一个邻居不属于本连通分量，那么它也是边界。
    - 只要满足以上任一条件，就将 (r, c) 加入 borders 列表。
    c. 对于当前像素 (r, c)，遍历它的四个邻居 (nr, nc)：
    - 如果邻居坐标合法（在网格内）、未被访问过、且其颜色 grid[nr][nc] == original_color，则将其加入队列，并标记为已访问。

  4. 着色：BFS 结束后，borders 列表中存储了所有需要修改的边界像素坐标。遍历这个列表，将 grid[r][c] 修改为 color。

  5. 返回结果：返回修改后的 grid。

步骤 4: 举例说明（以示例2为例）

  • 输入: grid = [[1,2,2],[2,3,2]], row=0, col=1, color=3
  • original_color = 2

BFS 过程:

  1. 起点 (0,1) 入队。
  2. 处理 (0,1):
    • 判断边界：r=0（在网格上边界），是边界。加入 borders。
    • 探索邻居：
      • 右(0,2)：颜色2，未访问，入队。
      • 下(1,1)：颜色3 ≠ 2，跳过。
      • 左(0,0)：颜色1 ≠ 2，跳过。
      • 上(-1,1)：越界，跳过。
  3. 处理 (0,2):
    • 判断边界：r=0 且 c=2（在右上角），是边界。加入 borders。
    • 探索邻居：
      • 右(0,3)：越界。
      • 下(1,2)：颜色2，未访问，入队。
      • 左(0,1)：已访问。
      • 上(-1,2)：越界。
  4. 处理 (1,2):
    • 判断边界：r=1 (最后一行)，是边界。加入 borders。
    • 探索邻居：
      • 右(1,3)：越界。
      • 下(2,2)：越界。
      • 左(1,1)：颜色3 ≠ 2，跳过。
      • 上(0,2)：已访问。
  5. 队列空，BFS结束。borders = [(0,1), (0,2), (1,2)]。
  6. 将这三个点的颜色改为3。得到 [[1,3,3],[2,3,3]]。

步骤 5: 复杂度与边界考虑

  • 时间复杂度：O(m * n)，最坏情况需要遍历整个网格。
  • 空间复杂度：O(m * n)，主要是队列和访问标记的开销。
  • 关键边界：
    1. 当 original_color == color 时，直接返回原矩阵。如果不做此判断，BFS在判断邻居颜色时会认为邻居颜色不同，导致错误地将所有像素判为边界，最终全改但颜色不变，虽然结果对但做了无用功，且在某些实现下可能引发循环。
    2. 注意数组下标范围。
    3. BFS中，必须在将邻居加入队列时立即标记为已访问，而不是在处理时才标记，否则可能导致同一节点被多次加入队列。

这个算法通过一次BFS遍历，同时完成了连通分量的探索和边界像素的识别，思路清晰，步骤分明。

LeetCode 1034. 边界着色 题目描述 给定一个大小为 m x n 的二维整数矩阵 grid ，表示一个网格。再给定一个整数 row , col 和一个整数 color 。矩阵中的每个值表示该位置像素的颜色。 “连通分量”定义为：从某个起始像素（坐标 (row, col) ）开始，所有与该像素颜色相同，并且通过水平或垂直方向（上、下、左、右）相邻连接的像素构成的区域。 “边界”是指连通分量中，满足以下任一条件的像素： 该像素位于整个网格的边界上（即行号为 0 或 m-1，或列号为 0 或 n-1）。 该像素在连通分量内部，但它的上、下、左、右四个相邻像素中，至少有一个像素的颜色与连通分量的颜色不同。 你的任务是：找到包含起始像素 (row, col) 的连通分量，并将这个连通分量中的所有边界像素的颜色，更改为 color 。 最终，你需要返回修改后的矩阵。 示例 1: 输入: grid = [ [ 1,1],[ 1,2] ], row = 0, col = 0, color = 3 输出: [ [ 3,3],[ 3,2] ] 解释: 起始像素颜色为1，连通分量是 (0,0) , (0,1) , (1,0) 。这个分量的边界是 (0,0) , (0,1) , (1,0) ，因为它们要么在网格边界上，要么有邻居颜色不是1。将边界改为3。中心(1,1)颜色是2，不属于此分量，不变。 示例 2: 输入: grid = [ [ 1,2,2],[ 2,3,2] ], row = 0, col = 1, color = 3 输出: [ [ 1,3,3],[ 2,3,3] ] 解释: 起始像素颜色为2。连通分量是 (0,1) , (0,2) , (1,2) 。边界像素是 (0,1) （邻居(0,0)颜色为1，不同）和 (0,2) , (1,2) （在网格边界上）。内部的(1,1)颜色为3，不属此分量。 (1,0) 颜色为2，但不与 (0,1) 四连通。 解题过程循序渐进讲解 步骤 1: 理解核心任务 题目核心是“查找连通分量”和“判断边界”。我们需要： 搜索 ：从 (row, col) 出发，找出所有颜色为 original_color = grid[row][col] 且与其四连通的像素坐标。这是一个“洪水填充”问题。 标记边界 ：在搜索过程中，对于遇到的每一个属于该连通分量的像素，判断它是否属于“边界”。 着色 ：将所有被标记为边界的像素，其颜色改为目标 color 。 步骤 2: 选择搜索算法 我们可以使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 。两者皆可，这里以 BFS 为例进行说明，因为它更直观，且无需担心递归深度问题。 使用一个队列 queue 来存储待访问的单元格坐标。 使用一个集合 visited 或一个与网格同大小的布尔数组，来记录已访问过的单元格，避免重复访问和死循环。 步骤 3: 详细设计 BFS 过程 初始化 ： 获取原始颜色 original_color = grid[row][col] 。如果 original_color 已经等于目标 color ，根据题意，可以直接返回原矩阵（避免不必要的修改和循环）。 初始化队列 queue ，将起始坐标 (row, col) 加入队列。 初始化访问标记（例如 m x n 的布尔矩阵 visited ），将起始点标记为已访问。 初始化一个列表 borders 用于存储所有边界像素的坐标。 方向数组 ：定义 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] 表示四个移动方向。 BFS 循环 （当队列不为空时）： a. 从队列中取出一个坐标 (r, c) 。 b. 关键：判断当前 (r, c) 是否为边界 。 - 条件1：如果 r == 0 或 r == m-1 或 c == 0 或 c == n-1 ，那么它在网格边界上，是边界。 - 条件2：检查其四个邻居。遍历 directions ，计算邻居坐标 (nr, nc) 。如果邻居坐标 不合法 （越界） 或者合法但其颜色不等于 original_color ，那么说明当前像素 (r, c) 至少有一个邻居不属于本连通分量，那么它也是边界。 - 只要满足以上任一条件，就将 (r, c) 加入 borders 列表。 c. 对于当前像素 (r, c) ，遍历它的四个邻居 (nr, nc) ： - 如果邻居坐标合法（在网格内）、 未被访问过 、且其颜色 grid[nr][nc] == original_color ，则将其加入队列，并标记为已访问。 着色 ：BFS 结束后， borders 列表中存储了所有需要修改的边界像素坐标。遍历这个列表，将 grid[r][c] 修改为 color 。 返回结果 ：返回修改后的 grid 。 步骤 4: 举例说明（以示例2为例） 输入: grid = [[1,2,2],[2,3,2]] , row=0 , col=1 , color=3 original_color = 2 BFS 过程 : 起点 (0,1) 入队。 处理 (0,1) : 判断边界： r=0 （在网格上边界），是边界。加入 borders 。 探索邻居： 右(0,2)：颜色2，未访问，入队。 下(1,1)：颜色3 ≠ 2，跳过。 左(0,0)：颜色1 ≠ 2，跳过。 上(-1,1)：越界，跳过。 处理 (0,2) : 判断边界： r=0 且 c=2 （在右上角），是边界。加入 borders 。 探索邻居： 右(0,3)：越界。 下(1,2)：颜色2，未访问，入队。 左(0,1)：已访问。 上(-1,2)：越界。 处理 (1,2) : 判断边界： r=1 (最后一行)，是边界。加入 borders 。 探索邻居： 右(1,3)：越界。 下(2,2)：越界。 左(1,1)：颜色3 ≠ 2，跳过。 上(0,2)：已访问。 队列空，BFS结束。 borders = [(0,1), (0,2), (1,2)] 。 将这三个点的颜色改为3。得到 [[1,3,3],[2,3,3]] 。 步骤 5: 复杂度与边界考虑 时间复杂度 ：O(m * n)，最坏情况需要遍历整个网格。 空间复杂度 ：O(m * n)，主要是队列和访问标记的开销。 关键边界 ： 当 original_color == color 时，直接返回原矩阵。如果不做此判断，BFS在判断邻居颜色时会认为邻居颜色不同，导致错误地将所有像素判为边界，最终全改但颜色不变，虽然结果对但做了无用功，且在某些实现下可能引发循环。 注意数组下标范围。 BFS中，必须在将邻居加入队列时 立即标记为已访问 ，而不是在处理时才标记，否则可能导致同一节点被多次加入队列。 这个算法通过一次BFS遍历，同时完成了连通分量的探索和边界像素的识别，思路清晰，步骤分明。