4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class SpecificPolyominoCovering
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	vector <string> findCovering(vector <string> region)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		try {
4fd800b3a8 2011-02-23        kinaba: 			rec(0, 0, region);
4fd800b3a8 2011-02-23        kinaba: 		} catch( vector<string>& r ) {
4fd800b3a8 2011-02-23        kinaba: 			return r;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return vector<string>();
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool nextX(int &y, int &x, vector<string>& r)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		while( r[y][x] != 'X' ) {
4fd800b3a8 2011-02-23        kinaba: 			++x;
4fd800b3a8 2011-02-23        kinaba: 			if( x == r[y].size() ) {
4fd800b3a8 2011-02-23        kinaba: 				x=0, ++y;
4fd800b3a8 2011-02-23        kinaba: 				if( y == r.size() )
4fd800b3a8 2011-02-23        kinaba: 					return false;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return true;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool canFill( vector<string> r )
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		return canFill_rec(0, 0, r);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	bool canFill_rec(int y, int x, vector<string>& r)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( !nextX(y, x, r) )
4fd800b3a8 2011-02-23        kinaba: 			return true;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// if it was the pattern fillable both by B and A,
4fd800b3a8 2011-02-23        kinaba: 		//     XX?X
4fd800b3a8 2011-02-23        kinaba: 		//     XXXX
4fd800b3a8 2011-02-23        kinaba: 		// then, if we can fill starting from A it implies ?=X
4fd800b3a8 2011-02-23        kinaba: 		// In this case, we must have been able to fill starting
4fd800b3a8 2011-02-23        kinaba: 		// from B. Thus, we never need to try A if we've failed
4fd800b3a8 2011-02-23        kinaba: 		// filling by B. The "lexicographically first" will by
4fd800b3a8 2011-02-23        kinaba: 		// considered elsewhere.
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( x+1 < r[y].size() && r[y][x+1]=='X' )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			r[y][x] = r[y][x+1] = 'B';
4fd800b3a8 2011-02-23        kinaba: 			return canFill_rec(y, x, r);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( x+3 < r[y].size() && y+1 < r.size() )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int py[] = {0,0,1,1,1,1};
4fd800b3a8 2011-02-23        kinaba: 			int px[] = {0,3,0,1,2,3};
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<6; ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( r[y+py[i]][x+px[i]]!='X' )
4fd800b3a8 2011-02-23        kinaba: 					return false;
4fd800b3a8 2011-02-23        kinaba: 				else
4fd800b3a8 2011-02-23        kinaba: 					r[y+py[i]][x+px[i]] = 'A';
4fd800b3a8 2011-02-23        kinaba: 			return canFill_rec(y, x, r);
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		return false;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	void rec(int y, int x, vector<string>& r)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( !nextX(y, x, r) )
4fd800b3a8 2011-02-23        kinaba: 			throw r;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		// try to fill by A
4fd800b3a8 2011-02-23        kinaba: 		if( x+3 < r[y].size() && y+1 < r.size() )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int py[] = {0,0,1,1,1,1};
4fd800b3a8 2011-02-23        kinaba: 			int px[] = {0,3,0,1,2,3};
4fd800b3a8 2011-02-23        kinaba: 			bool bad = false;
4fd800b3a8 2011-02-23        kinaba: 			for(int i=0; i<6; ++i)
4fd800b3a8 2011-02-23        kinaba: 				if( r[y+py[i]][x+px[i]]!='X' )
4fd800b3a8 2011-02-23        kinaba: 					bad = true;
4fd800b3a8 2011-02-23        kinaba: 			if( !bad )
4fd800b3a8 2011-02-23        kinaba: 			{
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<6; ++i)
4fd800b3a8 2011-02-23        kinaba: 					r[y+py[i]][x+px[i]] = 'A';
4fd800b3a8 2011-02-23        kinaba: 				if( canFill(r) )
4fd800b3a8 2011-02-23        kinaba: 					rec(y, x, r);
4fd800b3a8 2011-02-23        kinaba: 				for(int i=0; i<6; ++i)
4fd800b3a8 2011-02-23        kinaba: 					r[y+py[i]][x+px[i]] = 'X';
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		// try to fill by B
4fd800b3a8 2011-02-23        kinaba: 		if( x+1 < r[y].size() && r[y][x+1]=='X' )
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			r[y][x] = r[y][x+1] = 'B';
4fd800b3a8 2011-02-23        kinaba: 			rec(y, x, r);
4fd800b3a8 2011-02-23        kinaba: 			r[y][x] = r[y][x+1] = 'X';
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 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(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const vector <string> &Expected, const vector <string> &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: " << print_array(Expected) << endl; cerr << "\tReceived: " << print_array(Received) << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	string region_[] = {"XXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXX"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> region(region_, region_+sizeof(region_)/sizeof(*region_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal_[] = {"ABBA", "AAAA" };
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SpecificPolyominoCovering().findCovering(region)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	string region_[] = {"X..XXXX..X",
4fd800b3a8 2011-02-23        kinaba:  "XXXX..XXXX"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> region(region_, region_+sizeof(region_)/sizeof(*region_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal_[] = {"A..ABBA..A", "AAAA..AAAA" };
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SpecificPolyominoCovering().findCovering(region)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	string region_[] = {"XXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXX"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> region(region_, region_+sizeof(region_)/sizeof(*region_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal_[] = {"ABBABB", "AAAABB", "BBBBBB" };
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SpecificPolyominoCovering().findCovering(region)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	string region_[] = {"X..XX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXX"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> region(region_, region_+sizeof(region_)/sizeof(*region_));
4fd800b3a8 2011-02-23        kinaba: 	vector <string> RetVal;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SpecificPolyominoCovering().findCovering(region)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	string region_[] = {"XXXXXXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXX..XXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXXXXXX",
4fd800b3a8 2011-02-23        kinaba:  "XXXXXXXXXX"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> region(region_, region_+sizeof(region_)/sizeof(*region_));
4fd800b3a8 2011-02-23        kinaba: 	string RetVal_[] = {"ABBAABBABB", "AAAAAAAABB", "ABBABBBBBB", "AAAAA..ABB", "ABBAAAAABB", "AAAAABBABB", "BBBBAAAABB" };
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> RetVal(RetVal_, RetVal_+sizeof(RetVal_)/sizeof(*RetVal_));
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, SpecificPolyominoCovering().findCovering(region)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
4fd800b3a8 2011-02-23        kinaba: