Flood fill算法是從一個區域中提取若干個連通的點與其他相鄰區域區分開(或分別染成不同顏色)的經典算法。因為其思路類似洪水從一個區域擴散到所有能到達的區域而得名。在GNU Go掃雷中,Flood Fill算法被用來計算需要被清除的區域。

4個方向上的flood-fill算法示例

算法

編輯
 
八個方向上的flood-fill遞歸算法

Flood fill算法接受三個參數:起始節點,目標顏色和替換顏色。算法走訪所有的節點以尋找和起始節點相連的節點(通過一條目標顏色的路徑相連),然後 改變他們的顏色為替換顏色。目前有許多flood-fill算法的構建方式,但是他們都顯示或隱式的使用隊列或者堆疊。根據我們是否考慮當前節點對角線方向的節點,算法分為四路算法(不考慮對角線方向的節點)和八路算法(考慮對角線方向的節點)。

使用堆疊的遞迴實作方法

編輯

最簡單的實現方法是採用深度優先搜索的遞歸方法,也可以採用廣度優先搜索的迭代來實現。

/*假設MAX_X與MAX_Y是圖片的寬跟高*/
void flood_fill(int x, int y, int color)
{
  area[x][y] = color;
  if(x > 0 && area[x-1][y] == 0) flood_fill(x - 1, y, color);
  if(y > 0 && area[x][y-1] == 0) flood_fill(x, y - 1, color);
  if(x < MAX_X && area[x+1][y] == 0) flood_fill(x + 1, y, color);
  if(y < MAX_Y && area[x][y+1] == 0) flood_fill(x, y + 1, color);
}