Flood fill

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);
}