#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
typedef long long LL;
int dy[] = {-1,1, 0,0,-1,-1, 1,1};
int dx[] = { 0,0,-1,1,-1, 1,-1,1};
class LandAndSea
{
public:
vector<int> howManyIslands(vector<string> seaMap)
{
const int Y = seaMap.size();
const int X = seaMap[0].size();
// paint
vector< vector<int> > idMap(Y, vector<int>(X, -1));
int nIsland = 0;
for(int y=0; y<Y; ++y)
for(int x=0; x<X; ++x)
if( seaMap[y][x]=='x' && idMap[y][x]==-1 )
{
int id = (idMap[y][x] = nIsland++);
stack< pair<int,int> > S;
S.push( make_pair(y,x) );
while( !S.empty() ) {
pair<int,int> p = S.top(); S.pop();
for(int i=0; i<8; ++i) {
int yy = p.first +dy[i];
int xx = p.second+dx[i];
if( 0<=yy && yy<Y && 0<=xx && xx<X )
if( seaMap[yy][xx]=='x' && idMap[yy][xx]==-1 )
idMap[yy][xx] = id, S.push( make_pair(yy,xx) );
}
}
}
// I is contained by J
vector<int> refered(nIsland);
vector<int> ct(nIsland, -1);
set<int> outer_world;
while( outer_world.size() < nIsland )
{
set<int> outer2;
for(int I=0; I<nIsland; ++I)
if( !outer_world.count(I) )
{
stack< pair<int,int> > S;
set< pair<int,int> > vis;
for(int y=0; y<Y; ++y)
for(int x=0; x<X; ++x)
if( idMap[y][x] == I )
S.push( make_pair(y,x) ), vis.insert(S.top());
int sID = -1;
while( !S.empty() ) {
pair<int,int> p = S.top(); S.pop();
for(int i=0; i<4; ++i) {
int yy = p.first+dy[i];
int xx = p.second+dx[i];
if( !(0<=yy && yy<Y && 0<=xx && xx<X) )
goto notContained;
int ssID = idMap[yy][xx];
if( outer_world.count(ssID) )
{sID=ssID; goto notContained;}
pair<int,int> pp(yy,xx);
if( !vis.count(pp) && seaMap[yy][xx]=='.' )
S.push(pp), vis.insert(S.top());
}
}
continue;
notContained:
outer2.insert(I);
if(sID != -1) {
ct[I] = sID;
refered[sID]++;
}
}
outer_world.insert(outer2.begin(), outer2.end());
}
// topological sort
vector<int> level(nIsland, -1);
for(int L=0;;++L)
{
vector<int> victim;
for(int I=0; I<nIsland; ++I)
if( level[I] == -1 && refered[I] == 0 )
level[I] = L, victim.push_back(I);
if( victim.size() == 0 )
break;
for(int i=0; i<victim.size(); ++i)
{
int J = ct[victim[i]];
if( J != -1 )
refered[J]--;
}
}
vector<int> ans;
for(int i=0; i<level.size(); ++i) {
if( level[i]+1 > ans.size() )
ans.resize( level[i]+1 );
ans[level[i]]++;
}
return ans;
}
// BEGIN CUT HERE
public:
void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); }
private:
template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
void verify_case(int Case, const vector <int> &Expected, const vector <int> &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } }
void test_case_0() { string Arr0[] = {"x"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(0, Arg1, howManyIslands(Arg0)); }
void test_case_1() { string Arr0[] = {
"xxxxx",
"x...x",
"x.x.x",
"x...x",
"xxxxx"
}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(1, Arg1, howManyIslands(Arg0)); }
void test_case_2() { string Arr0[] = {
"xxxxx",
"x...x",
"x.x.x",
"x...x",
"xxxxx",
"xxxxx",
"x...x",
"x.x.x",
"x...x",
"xxxxx"
}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {2, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(2, Arg1, howManyIslands(Arg0)); }
void test_case_3() { string Arr0[] = {
"..",
".."
}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); vector <int> Arg1; verify_case(3, Arg1, howManyIslands(Arg0)); }
void test_case_4() { string Arr0[] = {
"............",
".......xxxx.",
"..xxx.x...x.",
"..x..x..x.x.",
"..x.x.x...x.",
"..xx...xxx.."
}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arr1[] = {1, 1 }; vector <int> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0]))); verify_case(4, Arg1, howManyIslands(Arg0)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main() { LandAndSea().run_test(-1); }
// END CUT HERE