需要帮助修改洪水填充算法吗

Question

我试图修改泛洪填充算法以返回最终的2D矩阵，其中所有color1只使用color2着色。注入应该从基质中的x，y开始。在

测试用例1：

在此之前：

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

在matrix = fill(matrix, x = 0, y = 2, color1 = 1, color2 = 2)之后

^{pr2}$

测试用例2：

在此之前：

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

在matrix = fill(matrix, x = 0, y = 0, color1 = 3, color2 = 1)之后

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

测试用例3：

在此之前：

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

在matrix = fill(matrix, x = 1, y = 2, color1 = 2, color2 = 1)之后

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

这与我在Invent with Python Blog发现的僵尸感染问题非常相似

目前，我有一个只修改全局矩阵的算法。在

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（），使其以in 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 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

任何帮助都将不胜感激。谢谢

Answer 1

只需返回矩阵：

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

或者，如果您不喜欢总是返回它，请使用包装器在最后只返回一次：

^{pr2}$

在这种情况下，您还可以去掉大多数参数。下面是我这样做的一个版本，它也使代码更简单：

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