Easy DFS Recursive Advanced Graphs
In plain English: Starting from a pixel, change its color and all connected same-color pixels to a new color (like the paint bucket tool).
DFS from the starting pixel, changing color as you go. Only recurse into neighbors that match the original color — naturally stops at boundaries.
Prompt
Given a 2D image grid, a starting pixel (sr, sc), and a new color, flood fill the connected region of the starting pixel's color with the new color.
Try to write it from scratch before scrolling down.
Solution
def flood_fill(image, sr, sc, new_color):
orig = image[sr][sc]
if orig == new_color:
return image
m, n = len(image), len(image[0])
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or image[i][j] != orig:
return
image[i][j] = new_color # fill
dfs(i+1, j); dfs(i-1, j); dfs(i, j+1); dfs(i, j-1)
dfs(sr, sc)
return image
# Test: flood_fill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2)
# => [[2,2,2],[2,2,0],[2,0,1]]