Flood Fill Algorithm

出處：http://acm.nudt.edu.cn/~twcourse/ConnectedComponentLabeling.html

Flood Fill Algorithm
Flood Fill Algorithm 的 flood 是指「淹水」， fill 是指「填滿」。

這個演算法的功用，舉例來說，就像是小畫家倒墨水的功能，將鄰近同顏色的區塊，一併染成同一個顏色。

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

如上圖左邊中間黑點，慢慢往四周圍擴散


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

1. int picture[11][21];    // 圖片的大小為 11x21，請參考上圖，寬長比!!
2.  
3. int flood(int x, int y, int fill_color, int original_color)
4. {
5.     if (x>=0 && x<11 && y>=0 && y<21)   // 不能超出邊界
6.         if (picture[x][y] == original_color)    // 顏色一樣才flood
7.         {
8.             picture[x][y] = fill_color;
9.             flood(x+1, y, fill_color, original_color);
10.             flood(x-1, y, fill_color, original_color);
11.             flood(x, y+1, fill_color, original_color);
12.             flood(x, y-1, fill_color, original_color);
13.         }
14. }
15.  
16. int main()
17. {
18.     // 在座標(5,4)的位置開始，淋上3號顏色。座標(5,4)即左圖黑點
19.     flood(5, 4, 3, picture[5][4]);
20. }

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

1. // 四個方向
2. const int dx[4] = {1, -1, 0, 0};
3. const int dy[4] = {0, 0, 1, -1};
4.  
5. // 判斷是否超出邊界
6. bool on_picture(int x, int y)   // 位於圖片上
7. {
8.     return x>=0 && x<11 && y>=0 && y<21;
9. }
10.  
11. void flood(int x, int y, int fill_color, int original_color)
12. {
13.     // 不能超出邊界
14.     if (!on_picture(x, y)) return;
15.  
16.     // 顏色一樣才flood
17.     if (picture[x][y] != original_color) return;
18.  
19.     picture[x][y] = fill_color;
20.     
21.     for (int i=0; i<4; i++)
22.     {
23.         // 求出下一個預定要淹沒的位置
24.         int next_x = x + dx[i], next_y = y + dy[i];
25.         flood(next_x, next_y, fill_color, original_color);
26.     }
27. }

實作時要特別注意，避免淹過水的地方又反反覆覆淹了很多次。這會使程式的效率大幅下降，其執行速度之慢，可讓程式在有生之年都不會結束。
言盡於此。這裡有許多類似於 Flood Fill Algorithm的演算法，可以參考：
http://www.codeproject.com/gdi/QuickFill.asp 

兩點是否在同一區塊

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

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

1. int picture[11][21];
2. bool visit[11][21]; // 新增一個二維陣列，紀錄淹到水的區域
3.  
4. void flood(int x, int y, int original_color)
5. {
6.     if (x>=0 && x<11 && y>=0 && y<21)
7.         if (picture[x][y] == original_color && !visit[x][y])
8.         {
9.             visit[x][y] = true;
10.             flood(x+1, y, original_color);
11.             flood(x-1, y, original_color);
12.             flood(x, y+1, original_color);
13.             flood(x, y-1, original_color);
14.        }
15. }
16.  
17. int main()
18. {
19.     // 初始化
20.     for (int i=0; i<11; i++)
21.         for (int j=0; j<21; j++)
22.             visit[i][j] = false;
23.     
24.     // 從其中一個點開始淹水，看看會不會淹到另一個點
25.     flood(5, 4);
26.  
27.     if (visit[10][10])
28.         cout << "兩點相連" << endl;
29.     else
30.         cout << "兩點不相連" << endl;
31. }

不同區塊的數目

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

1. int main()
2. {
3.     for (int i=0; i<11; i++)
4.         for (int j=0; j<21; j++)
5.             visit[i][j] = false;
6.             
7.     int count = 0;
8.     for (int x=0; x<11; x++)
9.         for (int y=0; y<21; y++)
10.             if (!visit[x][y])
11.             {
12.                 count++;
13.                 flood(x, y, picture[x][y]);
14.             }
15.  
16.     cout << "總共有" << count << "個區塊" << endl;
17. }

計算距離

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

1. int picture[11][21];
2. int dist[11][21];
3.  
4. void flood(int x, int y, int d, int original_color)
5. {
6.     if (x>=0 && x<11 && y>=0 && y<21)
7.         if (picture[x][y] == original_color && d < dist[x][y])
8.         {
9.             dist[x][y] = d;
10.             flood(x+1, y, d+1, original_color);
11.             flood(x-1, y, d+1, original_color);
12.             flood(x, y+1, d+1, original_color);
13.             flood(x, y-1, d+1, original_color);
14.         }
15. }
16.  
17. int main()
18. {
19.     for (int i=0; i<11; i++)
20.         for (int j=0; j<21; j++)
21.             dist[i][j] = 0;
22.         
23.     flood(5, 4, 0, picture[5][4]);  // 找出和座標(5,4)到其他點的距離
24. }

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

見下方：

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