UVa11094 - Continents(DFS)

題目大意：

有一個國王喜歡佔領領土，給你一張地圖，這張地圖左右邊是有相同連結的！請你找出除了國王所在的地方外，最大的一片土地，國王要去征戰他

提醒，由於國家的地圖沒有統一標準，因此陸地或是海洋的標示都不相同，但會給你國王所在地。

題目連結

觀念重點

• 理解題目英文
• 要讓 dfs 搜尋可以左邊邊界能與右邊邊界相通

分析

這題不難，只需要在 dfs 時特別判斷，碰到左右邊界時會連接到另一邊的邊界即可。

然後有一個小技巧，雖然你不知道陸地或海洋的字元，但是因為國王永遠都在陸地，所以可以假設國王所在地是陸地，那個字元就是陸地字元，那麼另外一個字元就是海洋，然後 DFS 即可。

參考來源

Uva11094 - Continents - txya900619

心得

這題沒有很難，但我原本想說我簡單快速看題目，結果出來的是 WA，在我百思不得其解時問了力瑋，他跟我說明這題題目大意，我才又認真地回去看發現自己一堆東西都漏看…，真不該相信自己的閱讀能力..。

可以用國王的位置當作陸地的字元這點是力瑋告訴我的，不然我一開始還真沒有想到，力瑋好聰明

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define MAXN 25 //最大值
#define BX 20 // 題目 X 最大邊界
#define BY 20 // 題目 Y 最大邊界
#define LOCAL
using namespace std;
int N, M, X, Y; //題目的輸入
char graph[MAXN][MAXN]; //題目的地圖 
char land, water; //陸地 與 水 的字元
string s; //輸入題目陣列元素用
 
int dfs(int x, int y){ //用來搜尋陸地區塊
    if(x < 0 || y < 0 || x >= N || y >= M) return 0; //超出邊界
    if(graph[x][y] != land) return 0; //如果這塊不是未被記錄的陸地就 return 
    graph[x][y] = '`'; //修改為已用過，由於題目的字元並不會用到此字元，因此改為她
    int cnt = 1; //表示這塊是陸地，所以必定會有 1
    cnt += dfs(x-1, y); //四個方向搜尋
    cnt += dfs(x+1, y);

    if(y == M-1) cnt += dfs(x, 0); //搜尋到右邊界，下次搜尋左邊界
    else cnt += dfs(x, y+1);

    if(y == 0) cnt += dfs(x,M-1); //搜尋到左邊界，下次搜尋右邊界
    else cnt += dfs(x, y-1);
    return cnt; //回傳陸地區塊
}

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

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

    while(cin >> N >> M){ //輸入資料
        for(int i = 0; i < N; i++){
            cin >> s;
            for(int j = 0; j < M; j++) graph[i][j] = s[j];
            //注意這裡的 s[j]，不是 s[i]
        }

        int ans = 0; //最大陸地
        cin >> X >> Y;
        land = graph[X][Y]; //判斷是 land 的字元
        dfs(X, Y);
        for(int i = 0; i < N; i++){ //遍地走訪
            for(int j = 0; j < M; j++){
                if(graph[i][j] == land) ans = max(ans, dfs(i, j));
                //如果此點有陸地，就全部搜尋看最大區塊是否有比 ans 大，有就更換答案
            }
        }
        //debug();
        cout << ans << '\n'; //輸出答案
    }
    return 0;
}