洪水填充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"]]

让我们继续这个例子并说用户决定新点,矩阵[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(矩阵,x,y),到目前为止我已经想出了这个:

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

你有办法引导我继续吗？试图在这里搜索SOF的洪水填充示例,但它们似乎不适合我的情况.至少我无法将这些示例应用于我的代码.洪水填充似乎不是那里受欢迎的主题......但是再次,帮助将非常感谢!

Answer 1

那么,洪水填充的想法是:

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)