#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
pair<int, short> dp[MAX_N][MAX_N][2];
bool a[MAX_N][MAX_N];
int n;
int solve(int cop, int robber, bool turn){
pair<int, short> &p = dp[cop][robber][turn];
if(cop == robber){
if(!turn){
return cop;
}
else{
return -1;
}
}
if(p.second >= 1){
return p.first;
}
if(p.second == 1){
if(!turn){
return -1;
}
else{
return robber;
}
}
p.second = 1;
p.first = -1;
if(!turn){
for(int i = 0; i < n; ++i){
if(a[i][cop] || i == cop){
int curr = solve(i, robber, !turn);
if(curr == -1){
p.first = i;
p.second = 2;
return p.first;
}
}
}
}
else{
for(int i = 0; i < n; ++i){
if(a[i][robber]){
int curr = solve(cop, i, !turn);
if(curr == -1){
p.first = i;
p.second = 2;
return p.first;
}
}
}
}
p.second = 2;
return p.first;
}
int cop;
int start(int N, bool A[MAX_N][MAX_N]){
n = N;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
a[i][j] = A[i][j];
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
solve(i, j, 0);
}
}
int sol = -1;
for(int i = 0; i < n; i++){
bool ok = true;
for(int j = 0; j < n; j++){
if(solve(i, j, 0) == -1){
ok = false;
break;
}
}
if(ok){
sol = i;
}
}
cop = sol;
return sol;
}
int nextMove(int R){
//cout << cop << " - " << R << endl;
cop = dp[cop][R][0].first;
//cout << cop << " -> " << R << endl << endl;
return cop;
}
/*
g++ "Baltic 14-coprobber.cpp" grader.cpp -std=c++11 -O2 -static -Wall -o coprobber
*/
/*
3
0 1 0
1 0 1
0 1 0
1
1 2 1 2
2 0 0 2
1 0 0 2
*/
