UVa722 - Lakes(DFS)

題目大意：

有一張地圖，我們會給你一個 x,y 座標，請你幫我們找出以此座標為基準、陸地為邊界擴大搜尋的水有幾格？

題目連結

重點觀念

• 學會理解英文會話題目
• DFS 的應用
• 如何配合題目輸入資料輸入

分析：

這題是簡單的 DFS 分析，其實應該是要使用 BFS 會更好些，避免遞迴崩潰的問題，但因為題目的地圖部會不會超過 \(99 * 99\)。

參考來源

Uva722 - Lakes txya900619

心得

這題簡單複習 DFS，加強自己的敏感度。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

注意，為了題目好寫，我將 0 設為陸地，1 設為水

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 120
#define LOCAL
using namespace std;
int graph[MAXN][MAXN]; //地圖
int cnt = 0, M, a, b, flag = 1; //cnt 計算水的數量、flag 判斷 output 輸出 '\n'
string temp; //用來輸入題目的地圖位置

void dfs(int x, int y){
    if(x < 0 || y < 0 || x > 100 || y > 100) return; //判斷邊界
    if(graph[x][y] == 0) return; //碰到陸地返回
    graph[x][y] = 0; //這邊的水被設為陸地，因為被記錄過
    cnt++; //增加計算水的樹木
    //cout << "cnt x y " << cnt << ' ' << x << ' ' << y << '\n';
    dfs(x-1, y); //四個方向進行搜尋
    dfs(x+1, y);
    dfs(x, y-1);
    dfs(x, y+1);
}

void print(){ //debug 輸出用
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < 100; j++) cout << graph[i][j] << ' ';
        cout << '\n';
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL

    cin >> M;
    while(M--){
        cin >> a >> b; //輸入要查詢的座標
        cin.ignore(); //這時候 cin 在 b 的尾端因此要 cin.ignore 來讓他直接指針指到下一個字元的前面。
        memset(graph, 0, sizeof(graph)); //重新整理，以免讓過去資料影響現在
        int i = 0; //表示輸入地圖到底幾行
        while(getline(cin,temp) && temp != ""){ //判斷是否有資料，沒有就是 temp == ""
            //cout << temp << '\n';
            for(int j = 0; j < temp.length(); j++) graph[i][j] = (temp[j] - '0') ^ 1; 
            //輸入資料，後面 ^ 1，這是方便運算， 0 ^ 1 = 1 就可以表示水
            //in my code 1 is water, 0 is land
            i++; //換下行輸入
        }
        cnt = 0; //重置計算水的數目
        //print();
        dfs(a-1, b-1); //由於我們題目 index 從 0 計算，因此 a, b 都減一
        if(flag == 1 ){ //這時候不需要中間空一行，因為是答案第一筆
            cout << cnt << '\n'; //輸出計算的水量
            flag = 0; //表示已經不是答案第一筆
        }
        else cout << "\n" << cnt << '\n'; //現在開始需要

    }
    return 0;
}