// BEGIN CUT HERE
// END CUT HERE
#line 5 "FoxAndGomoku.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctime>
using namespace std;
typedef long long ll;
int n,m;
bool vis[20][20],flag=false;
int dir_x[8]={1,-1,0,0,-1,-1,1,1};
int dir_y[8]={0,0,1,-1,1,-1,1,-1};
int X,Y;
bool inmap(int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<n) return true;
return false;
}
void dfs(int x,int y,int tot,vector<string> &board,int dir)
{
if(flag) return ;
if(tot>=4) { flag=true; return ; }
if(dir==-1)
{
for(int i=0;i<8;i++)
{
int X=x+dir_x;
int Y=y+dir_y;
if(inmap(X,Y))
{
if(board[X][Y]=='o'&&vis[X][Y]==false)
{
vis[X][Y]=true;
dfs(X,Y,tot+1,board,i);
vis[X][Y]=false;
}
}
}
}
else
{
int X=x+dir_x[dir];
int Y=y+dir_y[dir];
if(inmap(X,Y))
{
if(board[X][Y]=='o'&&vis[X][Y]==false)
{
vis[X][Y]=true;
dfs(X,Y,tot+1,board,dir);
vis[X][Y]=false;
}
}
}
return ;
}
class FoxAndGomoku
{
public:
string win(vector <string> board)
{
int i,j,k;
n=board.size();
vector<int> vt;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(board[j]=='o')
vt.push_back(i*n+j);
}
}
flag=false;
for(int i=0;i<vt.size();i++)
{
int x,y;
int u=vt;
x=u/n; y=u%n;
memset(vis,false,sizeof(vis));
vis[x][y]=true;
dfs(x,y,0,board,-1);
if(flag)
break;
}
string st;
if(flag)
st="found";
else
st="not found";
return st;
}
// 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(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); if ((Case == -1) || (Case == 7)) test_case_7(); if ((Case == -1) || (Case == 8)) test_case_8(); }
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 string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: "" << Expected << '"' << endl; cerr << "\tReceived: "" << Received << '"' << endl; } }
void test_case_0() { string Arr0[] = {"....o.",
"...o..",
"..o...",
".o....",
"o.....",
"......"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(0, Arg1, win(Arg0)); }
void test_case_1() { string Arr0[] = {"oooo.",
".oooo",
"oooo.",
".oooo",
"....."}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "not found"; verify_case(1, Arg1, win(Arg0)); }
void test_case_2() { string Arr0[] = {"oooo.",
".oooo",
"oooo.",
".oooo",
"....o"}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(2, Arg1, win(Arg0)); }
void test_case_3() { string Arr0[] = {"o.....",
".o....",
"..o...",
"...o..",
"....o.",
"......"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(3, Arg1, win(Arg0)); }
void test_case_4() { string Arr0[] = {"o....",
"o.o..",
"o.o.o",
"o.o..",
"o...."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(4, Arg1, win(Arg0)); }
void test_case_5() { string Arr0[] = {"..........",
"..........",
"..oooooo..",
"..o.......",
"..o.......",
"..oooooo..",
".......o..",
".......o..",
"..oooooo..",
".........."}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(5, Arg1, win(Arg0)); }
void test_case_6() { string Arr0[] = {"..........",
"..........",
"..oooo.o..",
"..o.......",
"..o.......",
"..o.oooo..",
".......o..",
".......o..",
"..oooo.o..",
".........."}
; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "not found"; verify_case(6, Arg1, win(Arg0)); }
void test_case_7() { string Arr0[] = {"ooooo",
"ooooo",
"ooooo",
"ooooo",
"ooooo"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "found"; verify_case(7, Arg1, win(Arg0)); }
void test_case_8() { string Arr0[] = {".....",
".....",
".....",
".....",
"....."}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); string Arg1 = "not found"; verify_case(8, Arg1, win(Arg0)); }
// END CUT HERE
};
// BEGIN CUT HERE
int main()
{
FoxAndGomoku ___test;
___test.run_test(-1);
return 0;
}
// END CUT HERE