2da323b3ad 2016-01-13        kinaba: #include <iostream>
2da323b3ad 2016-01-13        kinaba: #include <sstream>
2da323b3ad 2016-01-13        kinaba: #include <iomanip>
2da323b3ad 2016-01-13        kinaba: #include <vector>
2da323b3ad 2016-01-13        kinaba: #include <string>
2da323b3ad 2016-01-13        kinaba: #include <map>
2da323b3ad 2016-01-13        kinaba: #include <set>
2da323b3ad 2016-01-13        kinaba: #include <algorithm>
2da323b3ad 2016-01-13        kinaba: #include <numeric>
2da323b3ad 2016-01-13        kinaba: #include <iterator>
2da323b3ad 2016-01-13        kinaba: #include <functional>
2da323b3ad 2016-01-13        kinaba: #include <complex>
2da323b3ad 2016-01-13        kinaba: #include <queue>
2da323b3ad 2016-01-13        kinaba: #include <stack>
2da323b3ad 2016-01-13        kinaba: #include <cmath>
2da323b3ad 2016-01-13        kinaba: #include <cassert>
2da323b3ad 2016-01-13        kinaba: #include <tuple>
2da323b3ad 2016-01-13        kinaba: using namespace std;
2da323b3ad 2016-01-13        kinaba: typedef long long LL;
2da323b3ad 2016-01-13        kinaba: typedef complex<double> CMP;
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: int lsb(int x) {
2da323b3ad 2016-01-13        kinaba: 	for(int i=0 ;; ++i)
2da323b3ad 2016-01-13        kinaba: 		if(x&(1<<i))
2da323b3ad 2016-01-13        kinaba: 			return i;
2da323b3ad 2016-01-13        kinaba: }
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: class BoardEscape { public:
2da323b3ad 2016-01-13        kinaba: 	string findWinner(vector <string> s, int k)
2da323b3ad 2016-01-13        kinaba: 	{
2da323b3ad 2016-01-13        kinaba: 		const int H = s.size(), W = s[0].size();
2da323b3ad 2016-01-13        kinaba: 		const int dy[] = {-1,+1,0,0};
2da323b3ad 2016-01-13        kinaba: 		const int dx[] = {0,0,-1,+1};
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: 		vector<vector<vector<int>>> G_history;
2da323b3ad 2016-01-13        kinaba: 		for(int t=0; t<=256; ++t) {
2da323b3ad 2016-01-13        kinaba: 			vector<vector<int>> G(H, vector<int>(W));
2da323b3ad 2016-01-13        kinaba: 			for(int y=0; y<H; ++y)
2da323b3ad 2016-01-13        kinaba: 			for(int x=0; x<W; ++x) if(s[y][x]!='#') {
2da323b3ad 2016-01-13        kinaba: 				if(G_history.empty())
2da323b3ad 2016-01-13        kinaba: 					G[y][x] = 0;
2da323b3ad 2016-01-13        kinaba: 				else {
2da323b3ad 2016-01-13        kinaba: 					if(s[y][x]=='E')
2da323b3ad 2016-01-13        kinaba: 						G[y][x] = 0;
2da323b3ad 2016-01-13        kinaba: 					else {
2da323b3ad 2016-01-13        kinaba: 						int nf = 0xffffffff;
2da323b3ad 2016-01-13        kinaba: 						for(int _=0; _<4; ++_) {
2da323b3ad 2016-01-13        kinaba: 							int yy=y+dy[_], xx=x+dx[_];
2da323b3ad 2016-01-13        kinaba: 							if(0<=yy&&yy<H&&0<=xx&&xx<W&&s[yy][xx]!='#')
2da323b3ad 2016-01-13        kinaba: 								nf &= ~(1<<G_history.back()[yy][xx]);
2da323b3ad 2016-01-13        kinaba: 						}
2da323b3ad 2016-01-13        kinaba: 						G[y][x] = lsb(nf);
2da323b3ad 2016-01-13        kinaba: 					}
2da323b3ad 2016-01-13        kinaba: 				}
2da323b3ad 2016-01-13        kinaba: 			}
2da323b3ad 2016-01-13        kinaba: 			G_history.emplace_back(G);
2da323b3ad 2016-01-13        kinaba: 		}
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: 		int ans = 0;
2da323b3ad 2016-01-13        kinaba: 		for(int y=0; y<H; ++y)
2da323b3ad 2016-01-13        kinaba: 		for(int x=0; x<W; ++x) if(s[y][x]=='T') {
2da323b3ad 2016-01-13        kinaba: 			if(k < G_history.size())
2da323b3ad 2016-01-13        kinaba: 				ans ^= G_history[k][y][x];
2da323b3ad 2016-01-13        kinaba: 			else
2da323b3ad 2016-01-13        kinaba: 				ans ^= G_history[((k-1)%64)+193][y][x];
2da323b3ad 2016-01-13        kinaba: 		}
2da323b3ad 2016-01-13        kinaba: 		return (ans ? "Alice" : "Bob");
2da323b3ad 2016-01-13        kinaba: 	}
2da323b3ad 2016-01-13        kinaba: };
2da323b3ad 2016-01-13        kinaba: 
2da323b3ad 2016-01-13        kinaba: // BEGIN CUT HERE
2da323b3ad 2016-01-13        kinaba: #include <ctime>
2da323b3ad 2016-01-13        kinaba: double start_time; string timer()
2da323b3ad 2016-01-13        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
2da323b3ad 2016-01-13        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
2da323b3ad 2016-01-13        kinaba:  { os << "{ ";
2da323b3ad 2016-01-13        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
2da323b3ad 2016-01-13        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
2da323b3ad 2016-01-13        kinaba: void verify_case(const string& Expected, const string& Received) {
2da323b3ad 2016-01-13        kinaba:  bool ok = (Expected == Received);
2da323b3ad 2016-01-13        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
2da323b3ad 2016-01-13        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
2da323b3ad 2016-01-13        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
2da323b3ad 2016-01-13        kinaba: #define END	 verify_case(_, BoardEscape().findWinner(s, k));}
2da323b3ad 2016-01-13        kinaba: int main(){
2da323b3ad 2016-01-13        kinaba: CASE(0)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = {"TE"};
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = 2;
2da323b3ad 2016-01-13        kinaba: 	string _ = "Alice";
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: CASE(1)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = {"E#E",
2da323b3ad 2016-01-13        kinaba:  "#T#",
2da323b3ad 2016-01-13        kinaba:  "E#E"};
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = 1000000;
2da323b3ad 2016-01-13        kinaba: 	string _ = "Bob";
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: CASE(2)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = {"T.T.T.",
2da323b3ad 2016-01-13        kinaba:  ".E.E.E"};
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = 1;
2da323b3ad 2016-01-13        kinaba: 	string _ = "Alice";
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: CASE(3)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = {"TTE"};
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = 6;
2da323b3ad 2016-01-13        kinaba: 	string _ = "Alice";
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: CASE(4)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = {"..........................",
2da323b3ad 2016-01-13        kinaba:  "......TTT..TTT..T...T.....",
2da323b3ad 2016-01-13        kinaba:  ".....T.....T..T.TT.TT.....",
2da323b3ad 2016-01-13        kinaba:  "......TTT..TTT..T.T.T.....",
2da323b3ad 2016-01-13        kinaba:  ".........T.T.T..T...T.....",
2da323b3ad 2016-01-13        kinaba:  "......TTT..T..T.T...T.....",
2da323b3ad 2016-01-13        kinaba:  "..........................",
2da323b3ad 2016-01-13        kinaba:  "...E#E#E#E#E#E#E#E#E#E#...",
2da323b3ad 2016-01-13        kinaba:  "..........................",
2da323b3ad 2016-01-13        kinaba:  "......TTT..TTT...TTT......",
2da323b3ad 2016-01-13        kinaba:  ".....T........T.T.........",
2da323b3ad 2016-01-13        kinaba:  "......TTT.....T..TTT......",
2da323b3ad 2016-01-13        kinaba:  ".....T...T...T..T...T.....",
2da323b3ad 2016-01-13        kinaba:  "......TTT....T...TTT......",
2da323b3ad 2016-01-13        kinaba:  "..........................",
2da323b3ad 2016-01-13        kinaba:  "...#E#E#E#E#E#E#E#E#E#E...",
2da323b3ad 2016-01-13        kinaba:  "..........................",
2da323b3ad 2016-01-13        kinaba:  "....TT...T...T..T.TTT.T...",
2da323b3ad 2016-01-13        kinaba:  "...T.....T...T..T.T...T...",
2da323b3ad 2016-01-13        kinaba:  "...T.TT..T...TTTT.TT..T...",
2da323b3ad 2016-01-13        kinaba:  "...T..T..T...T..T.T.......",
2da323b3ad 2016-01-13        kinaba:  "....TT...TTT.T..T.T...T...",
2da323b3ad 2016-01-13        kinaba:  ".........................."};
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = 987654321;
2da323b3ad 2016-01-13        kinaba: 	string _ = "Bob";
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: /*
2da323b3ad 2016-01-13        kinaba: CASE(5)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = ;
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = ;
2da323b3ad 2016-01-13        kinaba: 	string _ = ;
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: CASE(6)
2da323b3ad 2016-01-13        kinaba: 	string s_[] = ;
2da323b3ad 2016-01-13        kinaba: 	  vector <string> s(s_, s_+sizeof(s_)/sizeof(*s_));
2da323b3ad 2016-01-13        kinaba: 	int k = ;
2da323b3ad 2016-01-13        kinaba: 	string _ = ;
2da323b3ad 2016-01-13        kinaba: END
2da323b3ad 2016-01-13        kinaba: */
2da323b3ad 2016-01-13        kinaba: }
2da323b3ad 2016-01-13        kinaba: // END CUT HERE