#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
struct State {
int cop, robber;
bool turn; // 1 = cop
State(int c = -1, int r = -1, bool t = -1) : cop(c), robber(r), turn(t) {}
operator int() const { return 2 * (MAX_N * cop + robber) + turn; }
};
vector<State> states, graph[8 * MAX_N * MAX_N];
bool win[8 * MAX_N * MAX_N];
int deg_in[8 * MAX_N * MAX_N];
State here, nxt[8 * MAX_N * MAX_N];
void add_edge(int a, int b, int c, int d, bool cop) {
graph[State(c, d, !cop)].push_back(State(a, b, cop));
deg_in[State(a, b, cop)]++;
}
int start(int N, bool A[MAX_N][MAX_N]) {
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
states.push_back(State(i, j, 0));
states.push_back(State(i, j, 1));
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
if (i == j) continue;
add_edge(i, j, i, j, 1);
for (int k = 0; k < N; k++) if (A[i][k]) {
add_edge(i, j, k, j, 1);
add_edge(j, i, j, k, 0);
}
}
queue<State> q; // Reverse BFS
for (State i : states) if (!deg_in[i]) {
q.push(i);
nxt[i] = i;
win[i] = true;
}
while (q.size()) {
State curr = q.front();
q.pop();
for (State i : graph[curr]) {
deg_in[i]--;
if (!win[i] && (i.turn || !deg_in[i])) {
nxt[i] = curr;
win[i] = true;
q.push(i);
}
}
}
for (int i = 0; i < N; i++) {
bool guarantee = true;
for (int j = 0; j < N; j++) guarantee &= win[State(i, j, 1)];
if (guarantee) {
here = {i, i, 1};
return i;
}
}
return -1;
}
int nextMove(int R) {
here.robber = R;
here.turn = 1;
here = nxt[here];
return here.cop;
}
