#include "coprobber.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 500;
const int M = 2 * maxN * maxN;
vector<int> g[maxN];
vector<int> g2[M];
//0 if it's officer's turn, 1 if robber's one
int enc(int officerPos, int robberPos, int whoseTurn) {
return whoseTurn * maxN * maxN + officerPos * maxN + robberPos;
}
void add(int v, int u) {
g2[v].push_back(u);
}
char vis[M];
int good[M];
int d[M];
void setGood(int cur) {
vis[cur] = 1;
if (g2[cur].empty()) {
good[cur] = maxN;
d[cur] = 0;
return;
}
char robberTurn = cur / (maxN * maxN);
good[cur] = -1;
for (int i : g2[cur]) {
if (!vis[i])
setGood(i);
if (good[i] != -1 && !robberTurn) {
if (good[cur] == -1 || d[good[cur]] > d[i])
good[cur] = i;
return;
} else if (good[i] == -1 && robberTurn)
return;
}
if (robberTurn)
good[cur] = g2[cur][0];
d[cur] = (good[cur] == -1) ? -1 : d[good[cur]] + 1;
}
int loc;
int start(int N, bool A[MAX_N][MAX_N]) {
memset(good, 0, sizeof good);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (A[i][j])
g[i].push_back(j);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (i != j) {
add(enc(i, j, 0), enc(i, j, 1));
for (int k : g[i])
add(enc(i, j, 0), enc(k, j, 1));
for (int k : g[j])
add(enc(i, j, 1), enc(i, k, 0));
}
memset(vis, 0, sizeof vis);
for (int i = 0; i < M; i++)
if (!vis[i])
setGood(i);
/*
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << good[enc(i, j, 0)] << " ";
cout << endl;
}
*/
for (int i = 0; i < N; i++) {
bool no = 0;
for (int j = 0; j < N; j++)
no |= good[enc(i, j, 0)] == -1;
if (!no) {
loc = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
//cout << loc << " " << R << endl;
loc = good[enc(loc, R, 0)] % (maxN * maxN) / maxN;
return loc;
}
