# Flood Fill - Graph / Matrix as Graph

My solution if anybody wants to check:

``````def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) -> List[List[int]]:
row, col = len(image), len(image[0])
visited = set([(r, c)])
colorToReplace = image[r][c]

def dfs(r, c):
if (r in range(row) and
c in range(col) and
image[r][c] == colorToReplace):
image[r][c] = replacement
directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
for dr, dc in directions:
dfs(r + dr, c + dc)

dfs(r, c)
return image
``````

I ran into a strange error, if I initialise my visited list as

`v = [[False] * num_cols] * num_rows`

Instead of how it is shown in the official solution, i.e.,

`v = [[False for c in range(num_cols)] for r in range(num_rows)]`

I cannot access or update some of the values in the `v`.

Can anyone try the same and explain what is happening?

Yep. Even the example shown is just giving an impression the neighbors of the input gets replaced a comprehensive example would have been with the following input and output
input:
8 1 3 4 1
3 8 8 3 3
6 7 8 8 3
8 2 8 9 1
12 8 1 3 2
output:
9 1 3 4 1
3 9 9 3 3
6 7 9 9 3
9 2 9 9 1
12 9 1 3 2

That’s beautiful. Thanks for sharing.

``````def get_neighbors(y, x, height, width):
for y_delta, x_delta in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
yi = y + y_delta
xi = x + x_delta
if 0 <= yi < height and 0 <= xi < width:
yield (yi, xi)

def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) -> List[List[int]]:
if len(image) == 0:
return []
stack = [(r, c)]
height = len(image)
width = len(image[0])
visited = set()
while stack:
y, x = stack.pop()
color = image[y][x]
image[y][x] = replacement
for yi, xi in get_neighbors(y, x, height, width):
if (yi, xi) in visited:
continue
if color != image[yi][xi]:
continue
stack.append((yi, xi))
return image

``````

Very simple dfs approach:

``````def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) -> List[List[int]]:
def dfs(r, c, color):
if r < 0 or c < 0 or r > len(image) - 1 or c > len(image[0]) - 1 or image[r][c] != color:
return
image[r][c] = replacement
dfs(r+1, c, color)
dfs(r, c+1, color)
dfs(r-1, c, color)
dfs(r, c-1, color)
dfs(r, c, image[r][c])
return image
``````