Flood Fill

LeetCode: https://leetcode.com/problems/flood-fill/

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value. Perform a flood fill starting from (sr, sc), replacing the starting pixel's color and all connected pixels of the same color with color.

Example:

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

1def floodFill(image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
2    rows, cols = len(image), len(image[0])
3    start = image[sr][sc]
4    if start == color:
5        return image
6    
7    def dfs(r: int, c: int) -> None:
8        if r < 0 or r >= rows or c < 0 or c >= cols:
9            return
10        if image[r][c] != start:
11            return
12        image[r][c] = color
13        dfs(r + 1, c)
14        dfs(r - 1, c)
15        dfs(r, c + 1)
16        dfs(r, c - 1)
17    
18    dfs(sr, sc)
19    return image

Number of Islands

Rotting Oranges

sr=1

sc=1

start=1

color=2

Step 1 / 3

Step 1:

Record the start color, repaint the start cell, and DFS/BFS outward to same-colored neighbors.

Focus: select @ [4]

sr=1sc=1start=1color=2