Flood Fill（图像渲染）

题目 / Problem

中文： 给定一个由 m × n 整数网格 image 表示的图像，其中 image[i][j] 表示图像中一个像素的颜色值。同时给定三个整数 sr、sc 和 color，请从像素 image[sr][sc] 开始执行泛洪填充。

泛洪填充的过程如下：
To perform a flood fill:

1. 从起始像素开始，将它的颜色修改为 color。
   Begin with the starting pixel and change its color to color.
2. 对与它直接相邻且颜色与起始像素原颜色相同的像素执行相同操作。直接相邻是指水平或垂直方向共享一条边，不包括对角线。
   Repeat the process for directly adjacent pixels that share the starting pixel's original color. Direct adjacency means sharing a side horizontally or vertically; diagonals are excluded.
3. 继续检查被修改像素的相邻像素，并修改所有与起始颜色相同的连通像素。
   Continue checking the neighbors of updated pixels and recolor every connected pixel matching the original color.
4. 当没有更多符合条件的相邻像素时停止。
   Stop when no more adjacent pixels of the original color remain.

返回执行泛洪填充后的图像。
Return the modified image after performing the flood fill.

English: You are given an image represented by an m × n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].

示例 / Examples

Example 1

Input:  image = [[1,1,1],
                 [1,1,0],
                 [1,0,1]],
        sr = 1, sc = 1, color = 2

Output: [[2,2,2],
         [2,2,0],
         [2,0,1]]

解释 / Explanation：

从位置 (sr, sc) = (1, 1) 开始，所有通过上下左右路径与起点相连、且颜色与起点原颜色 1 相同的像素都被修改为 2。
Starting from (sr, sc) = (1, 1), every pixel connected through a horizontal or vertical path and having the original color 1 is changed to 2.

右下角的 1 没有被修改，因为它只通过对角线与填充区域相邻，并不属于四方向连通区域。
The 1 in the bottom-right corner is not changed because it is connected to the filled region only diagonally, not horizontally or vertically.

填充前 / Before       填充后 / After

1  1  1              2  2  2
1 [1] 0       →      2 [2] 0
1  0  1              2  0  1

Example 2

Input:  image = [[0,0,0],
                 [0,0,0]],
        sr = 0, sc = 0, color = 0

Output: [[0,0,0],
         [0,0,0]]

解释 / Explanation： 起始像素的颜色已经是目标颜色 0，因此不需要修改图像。
The starting pixel already has the target color 0, so no changes are made.

约束 / Constraints

• m == image.length
• n == image[i].length
• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2¹⁶
• 0 <= sr < m
• 0 <= sc < n

解题思路：深度优先搜索 / Approach: Depth-First Search

首先保存起始像素的原颜色 originalColor。从 (sr, sc) 开始进行深度优先搜索，只访问满足以下条件的像素：
First, save the starting pixel's original color as originalColor. Starting from (sr, sc), perform a depth-first search and visit only pixels that:

• 位于图像边界内。
  Are inside the image boundaries.
• 颜色仍然等于 originalColor。
  Still have the value originalColor.
• 能够通过上、下、左、右方向与起始像素连通。
  Are connected to the starting pixel through up, down, left, or right moves.

访问一个像素时，立即将它改为 color。这不仅完成了填充，也相当于将它标记为“已访问”，因此不需要额外的 visited 数组。
When a pixel is visited, recolor it immediately. This performs the fill and also marks the pixel as visited, so a separate visited array is unnecessary.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} color
 * @return {number[][]}
 */
function floodFill(image, sr, sc, color) {
  const originalColor = image[sr][sc];

  // 新旧颜色相同时必须提前返回，否则无法用改色标记已访问节点。
  // Return early when both colors match; recoloring could not mark visits.
  if (originalColor === color) {
    return image;
  }

  const rows = image.length;
  const cols = image[0].length;
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function fill(row, col) {
    if (
      row < 0 ||
      row >= rows ||
      col < 0 ||
      col >= cols ||
      image[row][col] !== originalColor
    ) {
      return;
    }

    image[row][col] = color;

    for (const [rowOffset, colOffset] of directions) {
      fill(row + rowOffset, col + colOffset);
    }
  }

  fill(sr, sc);
  return image;
}

执行过程 / Walkthrough

对于 Example 1，起始位置为 (1, 1)，原颜色是 1，目标颜色是 2：
In Example 1, the starting position is (1, 1), the original color is 1, and the target color is 2:

值为 0 的像素会阻断搜索。位置 (2, 2) 虽然也是 1，但无法通过上下左右的同色路径到达，因此保持不变。
Pixels with value 0 block the search. Although (2, 2) also contains 1, no same-colored horizontal or vertical path reaches it, so it remains unchanged.

复杂度 / Complexity

设图像共有 m × n 个像素。
Let the image contain m × n pixels.

• 时间复杂度：O(mn)，最坏情况下需要访问图像中的每个像素。
  Time: O(mn), because every pixel may need to be visited in the worst case.
• 空间复杂度：O(mn)，最坏情况下递归调用栈可能包含所有像素。
  Space: O(mn), because the recursive call stack may contain all pixels in the worst case.

迭代解法：广度优先搜索 / Iterative Approach: BFS

也可以使用队列执行广度优先搜索，从起点开始逐层处理所有同色的相邻像素：
A queue can also perform a breadth-first search, processing all connected pixels of the original color level by level:

function floodFillBFS(image, sr, sc, color) {
  const originalColor = image[sr][sc];

  if (originalColor === color) {
    return image;
  }

  const rows = image.length;
  const cols = image[0].length;
  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  const queue = [[sr, sc]];
  let front = 0;

  image[sr][sc] = color;

  while (front < queue.length) {
    const [row, col] = queue[front++];

    for (const [rowOffset, colOffset] of directions) {
      const nextRow = row + rowOffset;
      const nextCol = col + colOffset;

      if (
        nextRow >= 0 &&
        nextRow < rows &&
        nextCol >= 0 &&
        nextCol < cols &&
        image[nextRow][nextCol] === originalColor
      ) {
        image[nextRow][nextCol] = color;
        queue.push([nextRow, nextCol]);
      }
    }
  }

  return image;
}

• 时间复杂度 / Time: O(mn)
• 空间复杂度 / Space: O(mn)

加入队列时就修改颜色，可以避免同一个像素被多个相邻像素重复加入队列。
Recoloring a pixel when it is enqueued prevents multiple neighbors from adding the same pixel to the queue repeatedly.

易错点 / Common Pitfalls

• 只考虑上下左右四个方向，不包括对角线。
  Consider only the four cardinal directions, not diagonals.
• 必须保存起始像素的原颜色，搜索过程中不能用不断变化的当前位置颜色作为判断标准。
  Save the starting pixel's original color; do not use a changing current color as the search criterion.
• 当 originalColor === color 时应立即返回，否则 DFS 或 BFS 可能重复访问像素并陷入无限循环。
  Return immediately when originalColor === color; otherwise DFS or BFS may revisit pixels indefinitely.
• 修改的是原数组，并返回同一个 image 引用。
  The original array is modified and the same image reference is returned.
• 访问相邻位置前必须检查行、列边界。
  Check row and column boundaries before accessing a neighboring position.