Artifact Content
Not logged in

Artifact bcf3463f5c537591c903ff74389120f098c9f7a6


#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