## Problem Statement#

An image is represented by an m x n integer grid image where `image[i][j]` represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill, consider the starting pixel, plus any pixels connected >4-directionally to the starting pixel of the same color as the starting pixel, >plus any pixels connected 4-directionally to those pixels (also with the same >color), and so on. Replace the color of all of the aforementioned pixels with color.

Return the modified image after performing the flood fill.

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

## Python Solution#

### DFS: Recursive#

``````class Solution:
def floodFill(self,
image: List[List[int]],
sr: int,
sc: int,
color: int) -> List[List[int]]:

ROWS, COLS = len(image), len(image[0])
s_color = image[sr][sc]
n_color = color

# Return the original image if the start color == new color
if s_color == n_color:
return image

def dfs(image, ro, co, s_color, n_color):
# Paint the cell if it is the start color
if image[ro][co] == s_color:
image[ro][co] = n_color

# Move up, right, down, left
for dr, dc in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
r = ro + dr
c = co + dc
# If the move is valid and the cell is the start color
if 0 <= r < ROWS and 0 <= c < COLS and image[r][c] == s_color:
dfs(image, r, c, s_color, n_color)

dfs(image, sr, sc, s_color, n_color)

return image
``````

Due to the recursive limits in Python, the iterative approach is superior.

### DFS: Iterative#

``````from collections import deque
class Solution:
def floodFill(self,
image: List[List[int]],
sr: int,
sc: int,
color: int) -> List[List[int]]:

ROWS, COLS = len(image), len(image[0])
s_color = image[sr][sc]
n_color = color

# Return the original image if start color == new color
if s_color == n_color:
return image

# Add the start coordinates to the stack
stack = deque([(sr, sc)])

while stack:
ro, co = stack.pop()
# If cell is the start color, paint it the new color
if image[ro][co] == s_color:
image[ro][co] = n_color

# Traverse up, right, down, and left
# (Note: We add the direcitons to the stack
#        in the reverse order)
for dr, dc in [(0, -1), (1, 0),  (0, 1), (-1, 0)]:
r = ro + dr
c = co + dc
# If move is valid and the next cell is the start color
if 0 <= r < ROWS and 0 <= c < COLS and image[r][c] == s_color:
stack.append((r, c))

return image
``````