实现泛洪填充算法

Question

我决定在我的应用程序中使用泛洪填充算法，使用维基百科中的伪代码：

Flood-fill (node, target-color, replacement-color):
     1. Set Q to the empty queue.
     2. If the color of node is not equal to target-color, return.
     3. Add node to Q.
     4. For each element n of Q:
     5.  If the color of n is equal to target-color:
     6.   Set w and e equal to n.
     7.   Move w to the west until the color of the node to the west of w no longer matches target-color.
     8.   Move e to the east until the color of the node to the east of e no longer matches target-color.
     9.   Set the color of nodes between w and e to replacement-color.
    10.   For each node n between w and e:
    11.    If the color of the node to the north of n is target-color, add that node to Q.
           If the color of the node to the south of n is target-color, add that node to Q.
    12. Continue looping until Q is exhausted.
    13. Return.

我一直做得很好，直到我点击了“继续循环直到Q被耗尽”。我不太明白。Q是如何耗尽的？

Answer 1

这是一种将递归函数转换为迭代函数的方法。不是将每个像素推入堆栈(递归)，而是将其添加到队列中。您说得对，这将扩展迭代的范围，但这正是您想要做的。当它找到与种子颜色匹配的新像素时，它会不断扩展。

如果我理解正确的话，您关心的是在使用"for each“语句时编辑队列的大小。算法伪代码在这方面是令人困惑的；其中它说：

For each element n of Q:
...
Continue looping until Q is exhausted.

你可以把它想象成：

while Q is not empty:
  dequeue element n of Q
  check the pixels

这将耗尽队列。

Answer 2

在处理Q中的节点之后(在步骤11之后，在返回循环之前)，删除它。最终，您将停止向Q添加元素，然后只需遍历其余的元素并逐个处理它们。