Flood Fill

Easy· DFS· Grid

Problem

You are given an image as a grid of integers, a starting pixel (sr, sc), and a new color. Recolor the starting pixel and every pixel connected to it 4-directionally that shares its original color, then return the image.

Examples

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]]

The bottom-right 1 is only diagonally connected, so it keeps its color.

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

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

Constraints

• 1 <= m, n <= 50
• 0 <= image[i][j], color < 2^16
• 0 <= sr < m, 0 <= sc < n

Hints & approach

Hint 1

Treat each pixel as a node connected to its four neighbours.

Hint 2

DFS from the start, only stepping onto pixels with the original color.

Hint 3

If the new color equals the original, return early or you will loop forever.

Approachtry the hints first

Record the original color at (sr, sc); if it already equals the new color, return the image unchanged. Otherwise run DFS or BFS from the start, recoloring each visited pixel and exploring the four neighbours that are in bounds and still hold the original color. Recoloring doubles as the visited marker, so no extra set is needed.

Time O(m * n) · Space O(m * n)

Next →Find if Path Exists in Graph