ZeroJudge E584: Continents

同題：UVa 11094 – Continents

Mijid 大帝是 Dodars 領土之王。他喜歡在自己領土內的城市之間旅行，您永遠不會看到他在同一個城市待超過一天。
因此，他佔領了他的大陸的所有領土！儘管如此，他還是不滿足於他領土上的所有城市，他希望能佔領另一片新大陸，以便有更多選擇去新城市。
現在，有了世界地圖，他需要您的幫助才能找到他所居住的大陸以外最大的大陸。
地圖的大小為 M x N，最多包含兩個不同的字母，分別表示土地和水域。
大陸是一組相連的陸地區域，被水域或地圖末端完全包圍。如果兩個區域具有共同的邊緣，則代表它們彼此相連。
左上區域的坐標為 (0, 0)，右下區域的坐標為 (M-1, N-1)。
由於地球是圓的，所以地圖最左區域 (x, 0) 和最右區域 (x, N-1) 相連。

範例測資

範例輸入範例輸出
EOF 輸入，每組測資的第一行包含兩個整數 M 和 N (M, N ≤ 20)。
接下來有 M 行 N 個字元的地圖。
接下來一行有兩個整數 X (0 ≤ X < M) 和 Y (0 ≤ Y < N)。
(X, Y) 代表 Mijid 大帝當前所在的區域的坐標。
每組測資之後有一個空白行。		對於每組測資，輸出一行 Mijid 大帝可以佔領的最大陸地區域。
5 5
wwwww
wwllw
wwwww
wllww
wwwww
1 3		2
ZeroJudge E584 範例測資

解題思路

使用 BFS 先找到大帝目前所在的大陸面積，大陸並沒有特定的字元，所以輸入中 X 和 Y 的座標上的字元就是大陸，其他都不是。

整張地圖是左右相連的，所以在跑 BFS 的時候要注意一下判斷式的條件。可以宣告一個二維陣列，裡面的資料都預設為 0，只要 BFS 有跑到這個點就將這個位置的數值設定為 1，跑 BFS 的過程如果跑到目前位置為 1 的點就不要繼續走下去，也不要將該點紀錄在可以佔領的區域數量中。

找完大帝所處的大陸之後就跑 M＊N 的迴圈，如果目前位置是大陸且沒有被走過，則以這個位置為起點跑 BFS，每次 BFS 結束之後回傳一個數字，為 BFS 跑到的點數量，也就是大陸面積，並且尋找最大的大陸面積。

範例程式碼－ZeroJudge E584: Continents

#include <iostream>
#include <vector>
using namespace std;

int M, N, MAP[50][50] = {};
string crater[50] = {};
char land;

int BFS(const vector<pair<int, int>>start, int count) {
    if (start.size() == 0) return count;
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++) {
        const int y = start[i].first, x = start[i].second;
        if (MAP[y][x] != 0) continue;
        MAP[y][x]++;
        count++;
        if (y - 1 >= 0 && crater[y-1][x] == land && MAP[y-1][x] == 0) newStart.push_back(make_pair(y-1, x));
        if (y + 1 < M && crater[y+1][x] == land && MAP[y+1][x] == 0) newStart.push_back(make_pair(y+1, x));
        if (x - 1 >= 0 && crater[y][x-1] == land && MAP[y][x-1] == 0) newStart.push_back(make_pair(y, x-1));
        else if (x - 1 < 0 && crater[y][N-1] == land && MAP[y][N-1] == 0) newStart.push_back(make_pair(y, N-1));
        if (x + 1 < N && crater[y][x+1] == land && MAP[y][x+1] == 0) newStart.push_back(make_pair(y, x+1));
        else if (x + 1 >= N && crater[y][0] == land && MAP[y][0] == 0) newStart.push_back(make_pair(y, 0));
    }
    return BFS(newStart, count);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> M >> N) {
        for (int i = 0; i<M; i++) {
            cin >> crater[i];
            for (int j = 0; j<N; j++) {
                MAP[i][j] = 0;
            }
        }
        int Y, X, ans = 0;
        cin >> Y >> X;
        land = crater[Y][X];
        vector<pair<int, int>>start;
        start.push_back(make_pair(Y, X));
        int ownLand = BFS(start, 0);
        for (int i = 0; i<M; i++) {
            for (int j = 0; j<N; j++) {
                if (crater[i][j] == land && MAP[i][j] == 0) {
                    vector<pair<int, int>>s;
                    s.push_back(make_pair(i, j));
                    ans = max(ans, BFS(s, 0));
                }
            }
        }
        cout << ans << "\n";
    }
}

//ZeroJudge E584
//Dr. SeanXD
標籤

相關文章

發佈留言