Disjoint Set-Union

srm764a.cpp

// Source: https://community.topcoder.com/stat?c=problem_statement&pm=15686
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

#define maxn (55 * 55)
static int parent[maxn];

int root(int v)
{
    while (v != parent[v])
    {
        parent[v] = parent[parent[v]]; // path compression
        v = parent[v];
    }
    return v;
}

// Quick-Union
void unite(int a, int b)
{
    a = root(a);
    b = root(b);
    parent[a] = b;
}

int longest(vector<string> &map)
{
    iota(parent, parent + maxn, 0);
    // calculate the dimension of the given map:
    int n = map.size();
    int m = map[0].size();

    // insert sentinels:
    for (auto &it : map)
        it = "." + it + ".";
    map.insert(begin(map), string(m + 2, '.'));
    map.insert(end(map), string(m + 2, '.'));

    // auxilary arrays to help in iteration:
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};

    // constructing islands:
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k];
                int y = j + dy[k];
                if (map[i][j] == 'X' && map[x][y] == 'X')
                    unite(i * m + j, x * m + y);
            }

    // calculating coastlines' size:
    vector<int> res(maxn);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (map[i][j] != 'X')
                continue;
            for (int k = 0; k < 4; k++)
            {
                int x = i + dx[k];
                int y = j + dy[k];
                if (map[x][y] == '.')
                    res[root(m * i + j)] += 1;
            }
        }
    return *max_element(begin(res), end(res));
}

int main(void)
{
    vector<string> map;
    string s;
    while (cin >> s)
        map.push_back(s);
    cout << longest(map) << endl;
}