Flood Fill - Graph / Matrix as Graph

Problems
28

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):
            visited.add((r, c))
            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
29

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?

30

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

31

That’s beautiful. Thanks for sharing.

32 
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
            visited.add((yi, xi))
            if color != image[yi][xi]:
                continue
            stack.append((yi, xi))
    return image
33

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