python - Python 中的洪水填充

Question

我对 Flood Fill 算法完全陌生。我从维基百科 ( http://en.wikipedia.org/wiki/Flood_fill ) 查了出来。但并没有变得那么聪明。我正在尝试在以下情况下使用它。我有一个矩阵:

matrix = [["a", "a", "b", "a", "a", "b"],
          ["a", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

然后我让用户从矩阵中决定一个点。如果在那个给定点是 "b" 什么都不做。在另一种情况下，如果给定点是 "a" 我想更改给定点和 所有周围或连接点 "a" 在洪水填充算法的帮助下到“c”。

例如，假设用户决定矩阵[0][0]。那么新矩阵将是:

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "a", "b", "a", "a", "b"],
          ["b", "a", "b", "a", "b", "b"],
          ["a", "a", "b", "a", "a", "a"],
          ["a", "b", "b", "a", "a", "b"]]

让我们继续这个例子，假设用户决定了新的点，matrix[3][1]。然后我们会:

matrix = [["c", "c", "b", "a", "a", "b"],
          ["c", "b", "b", "a", "b", "b"],
          ["b", "c", "b", "a", "a", "b"],
          ["b", "c", "b", "a", "b", "b"],
          ["c", "c", "b", "a", "a", "a"],
          ["c", "b", "b", "a", "a", "b"]]

我正在尝试构建一个函数 floodfill(matrix, x, y)，到目前为止我已经想出了这个:

def floodfill(matrix, x, y):
    if matrix[y][x] == "b":
        return matrix
    elif matrix[y][x] == ".":
        stack = []

你有办法引导我继续吗？试图查看此处 SOF 上的洪水填充示例，但它们似乎不适合我的情况。至少我无法将这些示例应用到我的代码中。洪水填充在这里似乎不是那个受欢迎的主题......但是再次强调，我们将不胜感激!

Answer 1

嗯，flood fill的思路是:

1. 检查点是否符合条件。
2. 如果是，将其更改为“c”(在您的情况下)- 并对周围的所有单元格调用填充。

类似 python 的伪代码:

def floodfill(matrix, x, y):
    #"hidden" stop clause - not reinvoking for "c" or "b", only for "a".
    if matrix[x][y] == "a":  
        matrix[x][y] = "c" 
        #recursively invoke flood fill on all surrounding cells:
        if x > 0:
            floodfill(matrix,x-1,y)
        if x < len(matrix[y]) - 1:
            floodfill(matrix,x+1,y)
        if y > 0:
            floodfill(matrix,x,y-1)
        if y < len(matrix) - 1:
            floodfill(matrix,x,y+1)