Flood fill

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

Flood fill演算法是從一個區域中提取若干個連通的點與其他相鄰區域區分開（或分別染成不同顏色）的經典演算法。因為其思路類似洪水從一個區域擴散到所有能到達的區域而得名。在GNU Go和踩地雷中，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);
}