Python 中的洪水填充 [英] Flood Fill in Python

问题描述

我完全不熟悉 Flood Fill 算法.我从维基百科 (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" 什么都不做.在另一种情况下，如果在给定的点是 "a" 我想改变给定的点和 所有周围或连接的点 "a" 在洪水填充算法的帮助下到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"]]

让我们继续那个例子，假设用户决定了新的点，矩阵 [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(matrix, 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 = []

你有办法引导我继续吗?试图查看 SOF 上的洪水填充示例，但它们似乎不适合我的情况.至少我无法将这些示例应用到我的代码中.洪水填充在这里似乎不是那么受欢迎的主题……但同样，我们将非常感谢您的帮助！

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"(在您的情况下) - 并对所有周围的单元格调用洪水填充.

类似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)

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