1034.边界着色

链接：1034.边界着色
难度：Medium
标签：深度优先搜索、广度优先搜索、数组、矩阵
简介：请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。

题解 1 - typescript

• 编辑时间：2021-12-07
• 执行用时：84ms
• 内存消耗：41.7MB
• 编程语言：typescript
• 解法介绍：dfs。

function colorBorder(grid: number[][], row: number, col: number, color: number): number[][] {
  const ori_color = grid[row][col];
  const m = grid.length;
  const n = grid[0].length;
  const list: number[][] = [];
  const set = new Set<string>();
  const format = (row: number, col: number) => `${row}:${col}`;
  draw(row, col);
  for (const [row, col] of list) grid[row][col] = color;
  return grid;
  function draw(row: number, col: number) {
    if (
      row < 0 ||
      row >= m ||
      col < 0 ||
      col >= n ||
      grid[row][col] !== ori_color ||
      set.has(format(row, col))
    )
      return;
    set.add(format(row, col));
    if (
      !(
        row > 0 &&
        col > 0 &&
        row < m - 1 &&
        col < n - 1 &&
        grid[row - 1][col] === ori_color &&
        grid[row + 1][col] === ori_color &&
        grid[row][col - 1] === ori_color &&
        grid[row][col + 1] === ori_color
      )
    ) {
      list.push([row, col]);
    }
    draw(row - 1, col);
    draw(row + 1, col);
    draw(row, col - 1);
    draw(row, col + 1);
  }
}