實施洪水填充算法

我決定用洪水填充算法我的應用程序，使用維基百科這個僞代碼：實施洪水填充算法

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如何用盡？

來源

2011-02-05 Voldemort

-1

在Q中處理完一個節點（在步驟11之後，回到循環之前）之後，將其刪除。最終，您將停止向Q添加元素，然後您只需完成其餘步驟並逐個處理它們。

來源

2011-02-05 20:22:19 Venge

但是，向Q添加節點是否會擴展For循環的迭代範圍？我認爲還有另一種語言，在類似的情況下，如果我這樣做，我會得到一個錯誤... – Voldemort 2011-02-05 20:55:39

這是一種將遞歸函數轉換爲迭代函數的方法。不是將每個像素都推送到堆棧（遞歸），而是將其添加到隊列中。你是對的，這將擴大迭代的範圍，但這就是你想要做的。隨着它找到與種子顏色相匹配的新像素，它不斷擴大。

如果我理解正確，則關注在使用「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

這將耗盡隊列。

來源

2011-02-13 04:34:40 Senior

實施洪水填充算法

回答

相關問題