485. Flood Fill
You are given an image as an m x n grid of integers image, where image[r][c] is the color of the pixel in row r, column c. You are also given a starting pixel (sr, sc) and a new color color.
Perform the paint-bucket operation every drawing app has: repaint the starting pixel and every pixel connected to it through side-sharing neighbors of the same original color. Concretely, let old be the color at (sr, sc) before painting. A pixel gets repainted to color if you can walk to it from (sr, sc) moving only up, down, left, or right, stepping only on pixels whose color is old. Diagonal contact does not connect pixels.
Return the image after the fill. If color is the same as the starting pixel's original color, the image comes back unchanged.
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: Starting at the center (row 1, col 1), every 1 reachable through up/down/left/right steps over 1s becomes 2. The 1 in the bottom-right corner only touches the region diagonally, so it keeps its color.
Example 2:
Input: image = [[0,0],[0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0],[0,0]]
Explanation: The new color equals the starting pixel's current color, so the fill changes nothing.
Constraints:
- 1 ≤ m, n ≤ 50
- 0 ≤ image[r][c], color < 2¹⁶
- 0 ≤ sr < m and 0 ≤ sc < n
Hints:
Think of the grid as a graph: each pixel is a node with up to four side-sharing neighbors. The pixels to repaint are exactly the connected component of (sr, sc) among pixels whose color equals the starting pixel's original color.
Traverse with DFS or BFS, repainting each pixel the moment you first reach it. The repaint doubles as your visited marker — a repainted pixel no longer matches the original color, so the traversal never returns to it.
One guard is essential: if color already equals the starting pixel's color, return immediately. Otherwise painted pixels still match the color you are searching for and the traversal never terminates.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Expected output: [[2,2,2],[2,2,0],[2,0,1]]