[程式競賽] UVa 572, Oil Deposits,Flood Fill 演算法

原題目簡述如下：
以 m x n 大小的 grid 代表一張地圖，現今要在此地圖內探勘，找出油田。某一區塊如果標示 "@" 代表有油，"*" 代表沒有油。
"@" 相鄰的區域的聯集，可視為一個油田。（所謂相鄰，除了上下左右，斜向的相鄰也算進去）
求任意地圖中，油田的個數。

例如輸入的測資為：
*    *   *    *  @
*   @  @  *  @
*   @   *   *  @
@ @  @   * @
@ @   *   *  @

則油田個數為 2。

想法
採用典型的倒水演算法（Flood Fill），走訪 "@" 出現的區域，從此往下倒水，倒過水的區域標上 id，因此透過 id 的編號，可以得知油田的個數。

實作
先實作倒水演算法的子函式：

void floodfill(vector<vector<char> >& map,
               vector<vector<int>  >& id_table,
               int row, int col, int id)
{
   if(row < 0 || (row >= map.size()) )   return;
   if(col < 0 || (col >= map[0].size())) return;
   if(map[row][col] != '@' || id_table[row][col] > 0) return;

   id_table[row][col] = id;
   floodfill(map, id_table, row-1, col-1, id);
   floodfill(map, id_table, row-1, col,   id);
   floodfill(map, id_table, row-1, col+1, id);
   floodfill(map, id_table, row,   col-1, id);
   floodfill(map, id_table, row,   col+1, id);
   floodfill(map, id_table, row+1, col-1, id);
   floodfill(map, id_table, row+1, col,   id);
   floodfill(map, id_table, row+1, col+1, id);
}

我透過 2D vector 來代表地圖，傳入要倒水位置的 row 和 column index，並先判斷當前位置是否出界，以及透過當前位置的 id 判斷是否已經被走訪過。如果沒有被走訪過，則標上新的 id 號碼，遞迴走訪相鄰 8 個區域。

在 main 主程式的部份，先做 stdin IO 將地圖讀入，動態地宣告 vector 陣列，然後將沒有走訪過的 "@" 區域，傳入 floodfill 開始倒水就可以了：

int main(int argc, char** argv)
{
    int m, n;
    string line;
    while(getline(cin, line))
    {
        istringstream token(line);
        token >> m >> n;
        if(m == 0 && n == 0) break;

        vector<vector<char> > map(m, vector<char>(n));
        vector<vector<int> >  id_table(m, vector<int>(n,0));

        for(int i=0; i<m; i++)
        {
            getline(cin, line);
            for(int j=0; j<n; j++)    map[i][j] = line[j];  
        }

        int id = 1;
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<n; j++)
            {
               if(map[i][j] == '@' && id_table[i][j] == 0)
               {
                   floodfill(map, id_table, i, j, id);
                   id++;
               }
            }
        }
        cout << (id-1) << endl;

    }
    return 0;

上傳 online judge 執行成功：

#		Problem	Verdict	Language	Run Time	Submission Date
23784822	572	Oil Deposits	Accepted	C++	0.000	2019-08-18 09:49:42