5

我对洪水填充算法完全陌生。我从 Wikipedia ( 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"将该给定点和所有周围或连接的点更改为“c”。"a"

例如，假设用户决定矩阵 [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 上的洪水填充示例，但它们似乎不适合我的情况。至少我无法将这些示例应用到我的代码中。在这里，洪水填充似乎不是那么受欢迎的主题......但同样，我们将非常感谢您的帮助！

4

2 回答 2

20

好吧，洪水填充的想法是：

  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)
于 2013-11-07T16:08:08.487 回答
2

在 Python 的图像处理库中有几种洪水填充算法的实现。我知道两个：skimage.segmentation.flood和OpenCV 的 floodFill。前者是在 Python 中使用类似于上面阿米特答案中的算法的算法实现的。后者是在 C++ 中使用概念上相似的算法实现的，但没有递归，因此效率更高（大图像大约是 25 倍）。

要使用 OpenCV 的 floodFill，您需要将矩阵转换为 np.array 整数，可以按如下方式完成：

import numpy as np
import cv2

matrix_np = np.asarray(matrix)
numeric_matrix = np.where(matrix_np=="a", 255, 0).astype(np.uint8)
mask = np.zeros(np.asarray(numeric_matrix.shape)+2, dtype=np.uint8)
start_pt = (y,x)
if matrix_np[start_pt]:
  cv2.floodFill(numeric_matrix, mask, start_pt, 255, flags=4)
mask = mask[1:-1, 1:-1]
matrix_np[mask==1] = "c"
matrix = matrix_np.tolist()

使用上面给出的示例矩阵和 x,y=(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']]
于 2019-11-26T10:25:58.200 回答