algorithm - Flood Fill算法的非递归实现？

Question

我正在使用 Java 开发一个小型绘图应用程序。我正在尝试通过实现 Flood Fill 算法来创建“桶填充”工具。

我尝试使用递归实现，但这是有问题的。不管怎样，我在网上搜索了一下，似乎为此目的，建议使用该算法的非递归实现。

所以我问你:

您能描述一下 Flood Fill 算法的非递归实现吗？欢迎提供实际的代码示例、一些伪代码，甚至是一般性解释。

我正在寻找您能想到的最简单的、或最有效的实现。

(不必特定于 Java)。

谢谢

Answer 1

我假设您有某种网格，您可以在其中接收要填充该区域的位置的坐标。

递归洪水填充算法是DFS。您可以执行 BFS 将其转换为非递归。

基本上，这两种算法的想法是相似的。您有一个袋子，其中保留了尚未看到的节点。您从包中删除一个节点并将该节点的有效邻居放回包中。如果袋子是一堆，你会得到一个 DFS。如果是队列，您将获得 BFS。

伪代码大概是这样

flood_fill(x,y, check_validity)
   //here check_validity is a function that given coordinates of the point tells you whether
   //the point should be colored or not
   Queue q
   q.push((x,y))
   while (q is not empty)
       (x1,y1) = q.pop()
       color(x1,y1)

       if (check_validity(x1+1,y1))
            q.push(x1+1,y1)
       if (check_validity(x1-1,y1))
            q.push(x1-1,y1)
       if (check_validity(x1,y1+1))
            q.push(x1,y1+1)
       if (check_validity(x1,y1-1))
            q.push(x1,y1-1)

注意:确保 check_validity 考虑到该点是否已经着色。

---

• DFS:深度优先搜索
• BFS:广度优先搜索