ZeroJudge E584: Continents

UVa 11094 – Continents

Emperor Mijid is the ruler of the Dodars territory. He enjoys traveling between cities within his domain, and you’ll never see him staying in the same city for more than a day. As a result, he has conquered all the territories on his continent! However, he is still not satisfied with all the cities on his land and wants to conquer another new continent so that he has more options for visiting new cities.
Now, with a world map in hand, he needs your help to find the largest continent other than the one he currently resides on.
The map has a size of M \times N and contains at most two different letters, representing land and water. A continent is a group of connected land areas, surrounded by water or the edge of the map. If two areas share a common edge, they are considered connected.
The top-left area has the coordinates (0, 0), and the bottom-right area has the coordinates (M-1, N-1). Since the Earth is round, the leftmost area (x, 0) and the rightmost area (x, N-1) are connected.

Sample Inputs/Outputs

Thought Process

Use BFS (Breadth-First Search) to first determine the area of the continent where the Emperor Mijid currently resides. Since the continent is not represented by a specific character, the character at the coordinates (X, Y) in the input will represent the land, and all other characters will represent non-land areas.

The entire map is connected from left to right, so when performing BFS, you need to carefully consider the conditions for traversal. You can declare a 2D array where each element is initially set to 0. During the BFS traversal, if a point is visited, set its corresponding value in the array to 1. If during BFS you encounter a point that already has a value of 1, skip that point and do not include it in the count of the conquerable area. This will ensure that BFS does not revisit points that have already been processed.

After identifying the continent where the emperor is located, you can loop through the entire M\*N grid. For each position, if it represents land and hasn't been visited yet, initiate a BFS starting from that position. After each BFS completes, return the number of points traversed, which corresponds to the continent's area. Track and compare these areas to find the maximum continent size. This method allows you to determine the largest conquerable landmass on the map, excluding the emperor's current continent.

Sample Code－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