在Python洪水填充 [英] Flood Fill in Python

问题描述

我complitely新颜色填充算法。我检查出来，从维基百科（ http://en.wikipedia.org/wiki/Flood_fill ） 。但并没有成为更为明智。我想用它在下列情况下。我有一个矩阵：

I'm complitely new to Flood Fill algorithm. I checked it out from Wikipedia (http://en.wikipedia.org/wiki/Flood_fill). But didn't become that much wiser. I'm trying to use it in following situation. I have a matrix:

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什么都不做。在如果在给定的点是一我想改变这种状况给定点和其他情况下的与所有周边或连接点一个 以C与洪水填充算法的帮助。

Then I let user to decide one point from matrix. If in that given point is "b" nothing is done. In the other case if in the given point is "a" I want to change that given point and all surrounding or connected points with "a" to "c" with help of flood fill algorithm.

例如假设用户决定矩阵[0] [0]。然后，新的矩阵是：

For example let's say user decides matrix[0][0]. Then new matrix would be:

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"]]

让我们继续这个例子，并说用户decieds新的点，矩阵[3] [1]。然后，我们将有：

Let's continue that example and say user decieds new point, matrix[3][1]. Then we would have:

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），至今我想出了这一点：

I'm trying to build a function floodfill(matrix, x, y) and so far I have come up with this:

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

你有办法使我继续吗？试图寻找在洪水填充的例子就在这里特种作战部队，但他们似乎没有适合我的情况。至少我没能应用这些例子，我的code。洪水填充似乎没有在这里是普遍的主题......但再次，帮助将是非常美联社preciated！

Do you have a way to lead me to proceed? Tried to look on flood fill examples on here SOF but they seemed not to fit my situation. At least I wasn't able to apply those examples to my code. Flood fill does not seem to be that popular subject here... But again, help would be highly appreciated!

推荐答案

嗯，洪水填充的理念是：

Well, the idea of flood fill is:

1. 检查点符合标准。
2. 如果是，将其更改为C（你的情况） - 和调用洪水填补所有周围的细胞

蟒蛇般的伪code：

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)

这篇关于在Python洪水填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！