Need help to modify flood fill algorithm

Question

I'm trying to modify the flood fill algorithm to return the final 2D matrix, where all color1 only is colored with color2. The flooding should start from x, y in the matrix.

Test case 1:

Before:

matrix = [[4, 3, 1, 2],
          [3, 1, 1, 2],
          [1, 2, 4, 5]]

After matrix = fill(matrix, x = 0, y = 2, color1 = 1, color2 = 2)

matrix = [[4, 3, 2, 2],
          [3, 2, 2, 2],
          [1, 2, 4, 5]]

Test case 2:

Before:

matrix = [[3, 2, 4],
          [5, 1, 4],
          [4, 3, 1]]

After matrix = fill(matrix, x = 0, y = 0, color1 = 3, color2 = 1)

matrix = [[1, 2, 4],
          [5, 1, 4],
          [4, 3, 1]]

Test case 3:

Before:

matrix = [[2, 1, 1],
          [2, 1, 2],
          [2, 2, 2]]

After matrix = fill(matrix, x = 1, y = 2, color1 = 2, color2 = 1)

matrix = [[1, 1, 1],
          [1, 1, 1],
          [1, 1, 1]]

This is very analogous to the Zombie infection problem I found at Invent with Python Blog

Currently, I have the algorithm that only modifies a global matrix.

def fill(matrix, x, y, color1, color2):

    matWidth = len(matrix)
    matHeight = len(matrix[0])
    if x < 0 or y < 0 or x >= matWidth or y >= matHeight:
        return  

    if matrix[x][y] == color2 or matrix[x][y] != color1:
        return
    if matrix[x][y] == color1:
        matrix[x][y] = color2

    fill(matrix, x - 1, y, color1, color2)
    fill(matrix, x + 1, y, color1, color2)
    fill(matrix, x, y - 1, color1, color2)
    fill(matrix, x, y + 1, color1, color2)

Is there a way to modify fill() in such a way that it takes in matrix as an argument and returns the final filled matrix?

Thanks a lot!

I'm very close to solving this. Here's my solution:

def fill(matrix, x, y, color1, color2):
    matWidth = len(matrix)
    matHeight = len(matrix[0])

    if x < 0 or y < 0 or x >= matWidth or y >= matHeight:
        return matrix  

    if mat[x][y] != color1:
        return matrix

    else:
        matrix[x][y] = color2
    if x == 0:
        if y == 0:
            if matrix[x + 1][y] == color1 and color[x + 1][y] != color2:
                matrix = fill(matrix, x + 1, y, color1, color2)
            if matrix[x][y + 1] == color1 and matrix[x][y + 1] != color2:
                matrix = fill(matrix, x, y + 1, color1, color2)
        if y == matHeight - 1:
            if matrix[x][y - 1] == color1 and matrix[x][y - 1] != color2:
                matrix = fill(matrix, x, y - 1, color1, color2)
            if matrix[x + 1][y] == color1 and matrix[x + 1][y] != color2:
                matrix = fill(matrix, x + 1, y, color1, color2)
        else:
            if matrix[x][y - 1] == color1 and matrix[x][y - 1] != color2:
                matrix = fill(matrix, x, y - 1, color1, color2)
            if matrix[x][y + 1] == color1 and matrix[x][y + 1] != color2:
                matrix = fill(matrix, x, y + 1, color1, color2)
            if matrix[x + 1][y] == color1 and matrix[x + 1][y] != color2:
                matrix = fill(matrix, x + 1, y, color1, color2)
    if x == matWidth - 1:
        if y == 0:
            if matrix[x - 1][y] == color1 and matrix[x - 1][y] != color2:
                matrix = fill(matrix, x - 1, y, color1, color2)
            if matrix[x][y + 1] == color1 and matrix[x][y + 1] != color2:
                matrix = fill(matrix, x, y + 1, color1, color2)
        if y == matHeight - 1:
            if matrix[x][y - 1] == color1 and matrix[x][y - 1] != color2:
                matrix = fill(matrix, x, y - 1, color1, color2)
            if matrix[x - 1][y] == color1 and matrix[x - 1][y] != color2:
                matrix = fill(matrix, x - 1, y, color1, color2)
        else:
            if matrix[x][y - 1] == color1 and matrix[x][y - 1] != color2:
                matrix = fill(matrix, x, y - 1, color1, color2)
            if matrix[x][y + 1] == color1 and matrix[x][y + 1] != color2:
                matrix = fill(matrix, x, y + 1, color1, color2)
            if matrix[x - 1][y] == color1 and matrix[x - 1][y] != color2:
                matrix = fill(matrix, x - 1, y, color1, color2)

    if y > 0 and matrix[x][y-1] == color1 and matrix[x][y-1] != color2:
        matrix = fill(matrix, x, y-1, color1, color2)

    if y < matHeight and matrix[x][y+1] == color1 and matrix[x][y+1] != color2:
        matrix = fill(matrix, x, y-1, color1, color2)

    if x < matWidth and matrix[x+1][y] == color1 and matrix[x+1][y] != color2:
        matrix = fill(matrix, x+1, y, color1, color2)

    if x > 0 and matrix[x-1][y] == color1 and matrix[x-1][y] != color2:
        matrix = fill(matrix, x-1, y, color1, color2)

    return matrix

Any help would be appreciated. Thanks

Answer 1

Simply return the matrix:

def fill(matrix, x, y, color1, color2):

    matWidth = len(matrix)
    matHeight = len(matrix[0])
    if x < 0 or y < 0 or x >= matWidth or y >= matHeight:
        return matrix

    if matrix[x][y] == color2 or matrix[x][y] != color1:
        return matrix
    if matrix[x][y] == color1:
        matrix[x][y] = color2

    fill(matrix, x - 1, y, color1, color2)
    fill(matrix, x + 1, y, color1, color2)
    fill(matrix, x, y - 1, color1, color2)
    fill(matrix, x, y + 1, color1, color2)

    return matrix

Or if you don't like always returning it, use a wrapper to only return it once at the end:

def fill(matrix, x, y, color1, color2):
    def fill(matrix, x, y, color1, color2):

        matWidth = len(matrix)
        matHeight = len(matrix[0])
        if x < 0 or y < 0 or x >= matWidth or y >= matHeight:
            return  

        if matrix[x][y] == color2 or matrix[x][y] != color1:
            return
        if matrix[x][y] == color1:
            matrix[x][y] = color2

        fill(matrix, x - 1, y, color1, color2)
        fill(matrix, x + 1, y, color1, color2)
        fill(matrix, x, y - 1, color1, color2)
        fill(matrix, x, y + 1, color1, color2)
    fill(matrix, x, y, color1, color2)
    return matrix

In that case you can also get rid of most parameters. Here's a version where I did that and also made the code a bit simpler:

def fill(matrix, x, y, color1, color2):
    def fill(x, y):
        if 0 <= x < matWidth and 0 <= y < matHeight and matrix[x][y] == color1:
            matrix[x][y] = color2
            fill(x - 1, y)
            fill(x + 1, y)
            fill(x, y - 1)
            fill(x, y + 1)
    matWidth = len(matrix)
    matHeight = len(matrix[0])
    fill(x, y)
    return matrix