Flood Fill
You are given an `m × n` integer grid `image` representing a picture. You are also given three integers `sr`, `sc`, and `color`. Perform a flood fill starting from pixel `(sr, sc)`: change the color of that pixel and all 4-directionally connected pixels of the same original color to `color`. Return the modified image. **Core Insight:** Classic DFS (or BFS) graph traversal on a grid. Starting from `(sr, sc)`, recursively visit all 4-directional neighbours that share the original color and repaint them. The key edge case: if the starting pixel already has the target color, return immediately to avoid infinite recursion. **Algorithm:** Record `origColor = image[sr][sc]`. If `origColor == color` return image unchanged. Define `dfs(r, c)`: if out of bounds or `image[r][c] != origColor` return. Set `image[r][c] = color`. Recurse on all 4 neighbours. Call `dfs(sr, sc)` and return image. **Complexity:** Time O(m × n) — each cell is visited at most once. Space O(m × n) — recursion stack in the worst case (entire grid is one connected region).
Constraints
- •
m == image.length - •
n == image[i].length - •
1 ≤ m, n ≤ 50
def floodFill(image: list[list[int]], sr: int, sc: int, color: int) -> list[list[int]]:
orig = image[sr][sc]
if orig == color:
return image
def dfs(r, c):
if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]): return
if image[r][c] != orig: return
image[r][c] = color
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
dfs(sr, sc)
return image