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

"""

# Initialize

queue = [(sr, sc)]

original_color = image[sr][sc]

m = len(image)

n = len(image[0])

# Sanity check

if original_color == color:

return image

# Main

while queue:

sr, sc = queue.pop(0)

if 0 <= sr < m and 0 <= sc < n:

if image[sr][sc] == original_color:

image[sr][sc] = color # change color

queue.append((sr-1, sc)) # up

queue.append((sr+1, sc)) # down

queue.append((sr, sc-1)) # left

queue.append((sr, sc+1)) # right

return image

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

"""

import collections

original_color, m, n = image[sr][sc], len(image), len(image[0])

if original_color != color:

queue = collections.deque([(sr, sc)]) # Doubly-Linked-List

while queue:

i, j = queue.popleft() # O(1) instead of O(N) from pop(0)

# Change Color

image[i][j] = color

# Up, Down, Left, Right

directions = ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1))

for x, y in directions:

if 0 <= x < m and 0 <= y < n and image[x][y] == original_color:

queue.append((x, y))

return image

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

"""

R, C = len(image), len(image[0])

original_color = image[sr][sc]

if original_color == color:

return image

def dfs(r, c):

if image[r][c] == original_color:

image[r][c] = color

if r >= 1:

dfs(r-1, c)

if r+1 < R:

dfs(r+1, c)

if c >= 1:

dfs(r, c-1)

if c+1 < C:

dfs(r, c+1)

dfs(sr, sc)