Flood Fill Algorithm

Flood Fill Algorithm

Flood Fill Algorithm的flood是指「淹水」,fill是指「填滿」。這個演算法的功用,舉例來說,就像是小畫家倒墨水的功能,將鄰近同顏色的區塊,一併染成同一個顏色。

電腦中的圖片,都是以一點一點的像素所組成的。簡單的來說,一張圖片,可以想做是一張方格紙,每個格子都對應到圖片上的一點像素。Flood Fill Algorithm會以某一格當做起點,開始向四周淹水,只要鄰近的格子是空的(顏色一樣的),水就會淹過去。

這裡提供一個簡單的程式碼。它往上下左右四個方向淹水。

亦可以將淹水的程式碼寫成這種風格:

實作時要特別注意,避免淹過水的地方又反反覆覆淹了很多次。這會使程式的效率大幅下降,其執行速度之慢,可讓程式在有生之年都不會結束。

言盡於此。這裡有許多類似於Flood Fill Algorithm的演算法,可以參考看看:http://www.codeproject.com/gdi/QuickFill.asp

兩點是否在同一區塊

Flood Fill Algorithm除了可以達到小畫家中倒墨水的效果之外,還可以找出地圖上某兩點是不是屬於同一區塊。

判斷座標(5,4)和座標(10,10)是不是屬於同一區塊的方法:

不同區塊的數目

找出這張圖總共有幾個區塊。只需修改一下main function:

計算距離

找出由某一點開始,到其他所有點的距離。常用來解決走迷宮之類的問題。

Flood Fill Algorithm應用廣泛。練習題目也不少。

UVa 260 280 352 469 572 601 657 776 782 784 785 871 10267 10336 10946