b98fbebb35 2011-09-14        kinaba: #include <iostream>
b98fbebb35 2011-09-14        kinaba: #include <sstream>
b98fbebb35 2011-09-14        kinaba: #include <iomanip>
b98fbebb35 2011-09-14        kinaba: #include <vector>
b98fbebb35 2011-09-14        kinaba: #include <string>
b98fbebb35 2011-09-14        kinaba: #include <map>
b98fbebb35 2011-09-14        kinaba: #include <set>
b98fbebb35 2011-09-14        kinaba: #include <algorithm>
b98fbebb35 2011-09-14        kinaba: #include <numeric>
b98fbebb35 2011-09-14        kinaba: #include <iterator>
b98fbebb35 2011-09-14        kinaba: #include <functional>
b98fbebb35 2011-09-14        kinaba: #include <complex>
b98fbebb35 2011-09-14        kinaba: #include <queue>
b98fbebb35 2011-09-14        kinaba: #include <stack>
b98fbebb35 2011-09-14        kinaba: #include <cmath>
b98fbebb35 2011-09-14        kinaba: #include <cassert>
b98fbebb35 2011-09-14        kinaba: #include <cstring>
b98fbebb35 2011-09-14        kinaba: using namespace std;
b98fbebb35 2011-09-14        kinaba: typedef long long LL;
b98fbebb35 2011-09-14        kinaba: typedef complex<double> CMP;
b98fbebb35 2011-09-14        kinaba: 
b98fbebb35 2011-09-14        kinaba: class ColorfulBoard { public:
b98fbebb35 2011-09-14        kinaba: 	int theMin(vector <string> board)
b98fbebb35 2011-09-14        kinaba: 	{
b98fbebb35 2011-09-14        kinaba: 		int H = board.size();
b98fbebb35 2011-09-14        kinaba: 		int W = board[0].size();
b98fbebb35 2011-09-14        kinaba: 
b98fbebb35 2011-09-14        kinaba: 		vector<bool> okY(H), okX(W);
b98fbebb35 2011-09-14        kinaba: 		for(bool changed=true; changed; )
b98fbebb35 2011-09-14        kinaba: 		{
b98fbebb35 2011-09-14        kinaba: 			changed = false;
b98fbebb35 2011-09-14        kinaba: 			for(int y=0; y<H; ++y) if(!okY[y])
b98fbebb35 2011-09-14        kinaba: 			{
b98fbebb35 2011-09-14        kinaba: 				set<char> cc(board[y].begin(), board[y].end());
b98fbebb35 2011-09-14        kinaba: 				cc.erase('*');
b98fbebb35 2011-09-14        kinaba: 				if( cc.size() == 1 ) {
b98fbebb35 2011-09-14        kinaba: 					okY[y] = changed = true;
b98fbebb35 2011-09-14        kinaba: 					for(int x=0; x<W; ++x)
b98fbebb35 2011-09-14        kinaba: 						board[y][x] = '*';
b98fbebb35 2011-09-14        kinaba: 				}
b98fbebb35 2011-09-14        kinaba: 			}
b98fbebb35 2011-09-14        kinaba: 			for(int x=0; x<W; ++x) if(!okX[x])
b98fbebb35 2011-09-14        kinaba: 			{
b98fbebb35 2011-09-14        kinaba: 				set<char> cc;
b98fbebb35 2011-09-14        kinaba: 				for(int y=0; y<H; ++y)
b98fbebb35 2011-09-14        kinaba: 					cc.insert(board[y][x]);
b98fbebb35 2011-09-14        kinaba: 				cc.erase('*');
b98fbebb35 2011-09-14        kinaba: 				if( cc.size() == 1 ) {
b98fbebb35 2011-09-14        kinaba: 					okX[x] = changed = true;
b98fbebb35 2011-09-14        kinaba: 					for(int y=0; y<H; ++y)
b98fbebb35 2011-09-14        kinaba: 						board[y][x] = '*';
b98fbebb35 2011-09-14        kinaba: 				}
b98fbebb35 2011-09-14        kinaba: 			}
b98fbebb35 2011-09-14        kinaba: 		}
b98fbebb35 2011-09-14        kinaba: 
b98fbebb35 2011-09-14        kinaba: 		int okys = 0;
b98fbebb35 2011-09-14        kinaba: 		for(int y=0; y<H; ++y)
b98fbebb35 2011-09-14        kinaba: 			if( okY[y] )
b98fbebb35 2011-09-14        kinaba: 				okys++;
b98fbebb35 2011-09-14        kinaba: 		int okxs = 0;
b98fbebb35 2011-09-14        kinaba: 		for(int x=0; x<W; ++x)
b98fbebb35 2011-09-14        kinaba: 			if( okX[x] )
b98fbebb35 2011-09-14        kinaba: 				okxs++;
b98fbebb35 2011-09-14        kinaba: 		if( okxs!=W && okys!=H )
b98fbebb35 2011-09-14        kinaba: 			return -1;
b98fbebb35 2011-09-14        kinaba: 		if( okxs!=W )
b98fbebb35 2011-09-14        kinaba: 			return okys;
b98fbebb35 2011-09-14        kinaba: 		if( okys!=H )
b98fbebb35 2011-09-14        kinaba: 			return okxs;
b98fbebb35 2011-09-14        kinaba: 		return min(okxs, okys);
b98fbebb35 2011-09-14        kinaba: 	}
b98fbebb35 2011-09-14        kinaba: };
b98fbebb35 2011-09-14        kinaba: 
b98fbebb35 2011-09-14        kinaba: // BEGIN CUT HERE
b98fbebb35 2011-09-14        kinaba: #include <ctime>
b98fbebb35 2011-09-14        kinaba: double start_time; string timer()
b98fbebb35 2011-09-14        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
b98fbebb35 2011-09-14        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
b98fbebb35 2011-09-14        kinaba:  { os << "{ ";
b98fbebb35 2011-09-14        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
b98fbebb35 2011-09-14        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
b98fbebb35 2011-09-14        kinaba: void verify_case(const int& Expected, const int& Received) {
b98fbebb35 2011-09-14        kinaba:  bool ok = (Expected == Received);
b98fbebb35 2011-09-14        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
b98fbebb35 2011-09-14        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
b98fbebb35 2011-09-14        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
b98fbebb35 2011-09-14        kinaba: #define END	 verify_case(_, ColorfulBoard().theMin(board));}
b98fbebb35 2011-09-14        kinaba: int main(){
b98fbebb35 2011-09-14        kinaba: 
b98fbebb35 2011-09-14        kinaba: CASE(0)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = {"SSS",
b98fbebb35 2011-09-14        kinaba:  "SRR",
b98fbebb35 2011-09-14        kinaba:  "SMM"};
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = 4;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: CASE(1)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = {"BBBBBBBB",
b98fbebb35 2011-09-14        kinaba:  "BBBBBBBB",
b98fbebb35 2011-09-14        kinaba:  "BBBBBBBB",
b98fbebb35 2011-09-14        kinaba:  "BBBBBBBB",
b98fbebb35 2011-09-14        kinaba:  "BBBBBBBB"};
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = 5;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: CASE(2)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = {"Ab",
b98fbebb35 2011-09-14        kinaba:  "bA"};
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = -1;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: CASE(3)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = {"iiiii",
b98fbebb35 2011-09-14        kinaba:  "iwiwi"}
b98fbebb35 2011-09-14        kinaba: ;
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = 4;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: CASE(4)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = {"ffffffffff",
b98fbebb35 2011-09-14        kinaba:  "xfxxoofoxo",
b98fbebb35 2011-09-14        kinaba:  "ffffffffff",
b98fbebb35 2011-09-14        kinaba:  "xfxxoofoxo",
b98fbebb35 2011-09-14        kinaba:  "ffffffffff",
b98fbebb35 2011-09-14        kinaba:  "ooxxoofoxo",
b98fbebb35 2011-09-14        kinaba:  "xfxxoofoxo",
b98fbebb35 2011-09-14        kinaba:  "xfxxoxfxxo",
b98fbebb35 2011-09-14        kinaba:  "ffxxofffxo",
b98fbebb35 2011-09-14        kinaba:  "xfxxoxfxxo"};
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = 17;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: /*
b98fbebb35 2011-09-14        kinaba: CASE(5)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = ;
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = ;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: CASE(6)
b98fbebb35 2011-09-14        kinaba: 	string board_[] = ;
b98fbebb35 2011-09-14        kinaba: 	  vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
b98fbebb35 2011-09-14        kinaba: 	int _ = ;
b98fbebb35 2011-09-14        kinaba: END
b98fbebb35 2011-09-14        kinaba: */
b98fbebb35 2011-09-14        kinaba: }
b98fbebb35 2011-09-14        kinaba: // END CUT HERE