TNotes.leetcode

Appearance

⏰1034. 边界着色【中等】

1034. 边界着色【中等】 ​

1. 📝 题目描述 ​

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

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

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

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

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

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

并返回最终的网格 grid。

示例 1：

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

示例 2：

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

示例 3：

txt
输入：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

2. 🎯 s.1 - DFS ​

js
/**
 * @param {number[][]} grid
 * @param {number} row
 * @param {number} col
 * @param {number} color
 * @return {number[][]}
 */
var colorBorder = function (grid, row, col, color) {
  const m = grid.length
  const n = grid[0].length
  const original = grid[row][col]
  const visited = Array.from({ length: m }, () => new Array(n).fill(false))
  const borders = []
  const dirs = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ]

  const dfs = (i, j) => {
    visited[i][j] = true
    let isBorder = false
    for (const [di, dj] of dirs) {
      const ni = i + di
      const nj = j + dj
      if (ni < 0 || ni >= m || nj < 0 || nj >= n || grid[ni][nj] !== original) {
        isBorder = true
      } else if (!visited[ni][nj]) {
        dfs(ni, nj)
      }
    }
    if (isBorder) borders.push([i, j])
  }

  dfs(row, col)
  for (const [i, j] of borders) grid[i][j] = color
  return grid
}
  • 时间复杂度：O(m×n)，其中 m 和 n 分别是矩阵的行数和列数
  • 空间复杂度：O(m×n)，访问标记数组和递归栈

算法思路：

  • 从 (row, col) 出发进行 DFS，找出所有与其同色的连通分量
  • 对于每个节点，检查它是否是边界（相邻位置越界或颜色不同）
  • 收集所有边界节点，最后统一着色