76db68d634 2018-07-28        kinaba: #include <iostream>
76db68d634 2018-07-28        kinaba: #include <sstream>
76db68d634 2018-07-28        kinaba: #include <iomanip>
76db68d634 2018-07-28        kinaba: #include <vector>
76db68d634 2018-07-28        kinaba: #include <string>
76db68d634 2018-07-28        kinaba: #include <map>
76db68d634 2018-07-28        kinaba: #include <set>
76db68d634 2018-07-28        kinaba: #include <algorithm>
76db68d634 2018-07-28        kinaba: #include <numeric>
76db68d634 2018-07-28        kinaba: #include <iterator>
76db68d634 2018-07-28        kinaba: #include <functional>
76db68d634 2018-07-28        kinaba: #include <complex>
76db68d634 2018-07-28        kinaba: #include <queue>
76db68d634 2018-07-28        kinaba: #include <stack>
76db68d634 2018-07-28        kinaba: #include <cmath>
76db68d634 2018-07-28        kinaba: #include <cassert>
76db68d634 2018-07-28        kinaba: #include <tuple>
76db68d634 2018-07-28        kinaba: using namespace std;
76db68d634 2018-07-28        kinaba: typedef long long LL;
76db68d634 2018-07-28        kinaba: typedef complex<double> CMP;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: class SquareCutout { public:
76db68d634 2018-07-28        kinaba: 	int verify(vector <string> cutout)
76db68d634 2018-07-28        kinaba: 	{
76db68d634 2018-07-28        kinaba: 		const int Y = cutout.size(), X = cutout[0].size();
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		bool has_black = false;
76db68d634 2018-07-28        kinaba: 		for (int y = 0; y < Y; ++y)
76db68d634 2018-07-28        kinaba: 			for (int x = 0; x < X; ++x)
76db68d634 2018-07-28        kinaba: 				if (cutout[y][x] == '#')
76db68d634 2018-07-28        kinaba: 					has_black = true;
76db68d634 2018-07-28        kinaba: 		if (!has_black)
76db68d634 2018-07-28        kinaba: 			return 1;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		int ym = Y, xm = X, yM = 0, xM = 0;
76db68d634 2018-07-28        kinaba: 		for (int y = 0; y < Y; ++y)
76db68d634 2018-07-28        kinaba: 			for (int x = 0; x < X; ++x)
76db68d634 2018-07-28        kinaba: 				if (cutout[y][x] == '#')
76db68d634 2018-07-28        kinaba: 					ym = min(ym, y), yM = max(yM, y), xm = min(xm, x), xM = max(xM, x);
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		for (int y = ym; y <= yM; ++y)
76db68d634 2018-07-28        kinaba: 			for (int x = xm; x <= xM; ++x)
76db68d634 2018-07-28        kinaba: 				if (cutout[y][x] != '#')
76db68d634 2018-07-28        kinaba: 					return 0;
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: 		bool x_extendable = (xm == 0 || xM == X - 1);
76db68d634 2018-07-28        kinaba: 		bool y_extendable = (ym == 0 || yM == Y - 1);
76db68d634 2018-07-28        kinaba: 		int yy = yM - ym + 1;
76db68d634 2018-07-28        kinaba: 		int xx = xM - xm + 1;
76db68d634 2018-07-28        kinaba: 		if (yy == xx)
76db68d634 2018-07-28        kinaba: 			return yy;
76db68d634 2018-07-28        kinaba: 		if (yy < xx)
76db68d634 2018-07-28        kinaba: 			return y_extendable ? xx : 0;
76db68d634 2018-07-28        kinaba: 		return x_extendable ? yy : 0;
76db68d634 2018-07-28        kinaba: 	}
76db68d634 2018-07-28        kinaba: };
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: // BEGIN CUT HERE
76db68d634 2018-07-28        kinaba: #include <ctime>
76db68d634 2018-07-28        kinaba: double start_time; string timer()
76db68d634 2018-07-28        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
76db68d634 2018-07-28        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
76db68d634 2018-07-28        kinaba:  { os << "{ ";
76db68d634 2018-07-28        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
76db68d634 2018-07-28        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
76db68d634 2018-07-28        kinaba: void verify_case(const int& Expected, const int& Received) {
76db68d634 2018-07-28        kinaba:  bool ok = (Expected == Received);
76db68d634 2018-07-28        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
76db68d634 2018-07-28        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
76db68d634 2018-07-28        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
76db68d634 2018-07-28        kinaba: #define END	 verify_case(_, SquareCutout().verify(cutout));}
76db68d634 2018-07-28        kinaba: int main(){
76db68d634 2018-07-28        kinaba: 
76db68d634 2018-07-28        kinaba: CASE(0)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = {".....",
76db68d634 2018-07-28        kinaba:  "..##.",
76db68d634 2018-07-28        kinaba:  "..##.",
76db68d634 2018-07-28        kinaba:  ".....",
76db68d634 2018-07-28        kinaba:  "....."};
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 2;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(1)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = {"...",
76db68d634 2018-07-28        kinaba:  "..."};
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 1;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(2)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = {".....",
76db68d634 2018-07-28        kinaba:  ".###.",
76db68d634 2018-07-28        kinaba:  ".#.#.",
76db68d634 2018-07-28        kinaba:  ".###.",
76db68d634 2018-07-28        kinaba:  "....."};
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 0;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(3)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = {"..####",
76db68d634 2018-07-28        kinaba:  "..####",
76db68d634 2018-07-28        kinaba:  "......"};
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 4;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(4)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = {"..#..",
76db68d634 2018-07-28        kinaba:  ".###.",
76db68d634 2018-07-28        kinaba:  "#####",
76db68d634 2018-07-28        kinaba:  ".###.",
76db68d634 2018-07-28        kinaba:  "..#.."};
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 0;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: CASE(5)
76db68d634 2018-07-28        kinaba: string cutout_[] = { "...", "...", "..." };
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = 1;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: /*
76db68d634 2018-07-28        kinaba: CASE(6)
76db68d634 2018-07-28        kinaba: 	string cutout_[] = ;
76db68d634 2018-07-28        kinaba: 	  vector <string> cutout(cutout_, cutout_+sizeof(cutout_)/sizeof(*cutout_));
76db68d634 2018-07-28        kinaba: 	int _ = ;
76db68d634 2018-07-28        kinaba: END
76db68d634 2018-07-28        kinaba: */
76db68d634 2018-07-28        kinaba: }
76db68d634 2018-07-28        kinaba: // END CUT HERE