#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
void _debug_cerr(const char* name, T&& value) {
cerr << name << ": " << value << '\n';
}
template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
const char* comma = strchr(names, ',');
cerr.write(names, comma - names) << ": " << value << ", ";
_debug_cerr(comma + 1, forward<Args>(args)...);
}
#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)
struct Node
{
int16_t cop, robber;
bool type;
Node(int16_t c, int16_t r, bool t) : cop(c), robber(r), type(t) {}
};
//graph[cop][robber][0 = cop moves next, 1 = r]
//vector<Node> graph[503][503][2];
//vector<Node> reverse_graph[503][503][2];
bool can_win[503][503][2];
int deg[503][503];
int arr[503][503]; // given current move is police and arr[cop cur][r] where should cop go
int police_current;
int start(int n, bool A[MAX_N][MAX_N])
{
queue<Node> q;
// graph construction
for(int i = 0; i < n; i ++)
{
for(int j = 0; j <n; j ++)
{
can_win[i][j][0] = can_win[i][j][1] = false;
if(i == j)
{
can_win[i][j][0] = can_win[i][j][1] = true;
q.push(Node(i, j, 1));
q.push(Node(i, j, 0));
}
}
}
for(int i = 0; i < n; i ++) // for every cop pos
{
for(int j = 0; j < n; j ++) // for every r pos
{
if(i == j){continue;}
for(int p = 0; p<n; p ++) // for every new position police can move to on a police move first node
{
if(A[i][p] == 1 || i == p)
{
Node temp(p, j, 1);
//graph[i][j][0].push_back(temp);
temp = Node(i, j, 0);
//reverse_graph[p][j][1].push_back(temp);
}
}
for(int c = 0; c < n; c ++) // for every possible move on the robber move first
{
if(A[j][c] == 1)
{
Node temp(i, c, 0);
//graph[i][j][1].push_back(temp);
deg[i][j] ++;
temp = Node(i, j, 1);
//reverse_graph[i][c][0].push_back(temp);
}
}
}
}
/*
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
debug(i, j);
for(auto v: reverse_graph[i][j][0])
{
debug(v.cop, v.robber, v.type);
}
}
}
cerr << " roober mover \n";
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n; j ++)
{
debug(i, j);
for(auto v: reverse_graph[i][j][1])
{
debug(v.cop, v.robber, v.type);
}
}
}
*/
//bfs
while(!q.empty())
{
Node cur = q.front();
q.pop();
//debug(cur.cop, cur.robber, cur.type);
if(cur.type == 0) // if cop is goin now i.e. robber went before
{
for(int i = 0; i < n; i ++)
{
if(A[i][cur.robber])
{
Node v(cur.cop, i, 1);
// if this neighbour is already visited and winnable, dont consider it
if(can_win[v.cop][v.robber][v.type] == true)
{
continue;
}
deg[v.cop][v.robber] --;
if(deg[v.cop][v.robber]== 0)
{
//debug(can_win[v.cop][v.robber][v.type] = true);
can_win[v.cop][v.robber][v.type] = true;
q.push(v);
}
}
}
}
else // if prev state was a cop move state and cop has agency to get to this state
{
for(int i = 0; i < n; i ++) // previous move was a cop move
{
if(A[i][cur.cop] == 1 || i == cur.cop)
{
Node v(i, cur.robber, 0);
can_win[v.cop][v.robber][v.type] = true;
//debug(can_win[v.cop][v.robber][v.type] = true);
arr[v.cop][v.robber] = cur.cop;
q.push(v);
}
}
}
}
// determine answer and output
bool valid = true;
for(int i = 0; i < n; i ++)
{
valid = true;
police_current = i;
for(int j = 0; j < n; j ++)
{
if(!can_win[i][j][0])
{
valid = false;
break;
}
}
}
if(valid)
{
return police_current;
}
return -1;
//bfs to determine which positions are winning positions
// 1. create a queue with all known winning positions
// 2. use reverse graph to find neighbours, if your neighbour is a police move first node then mark it as true, and add to bfs
//3. if your neighbour is a rober move first node,
//a) keep track of its degree and -1 each time you have visited
// if deg == 0 then ,mark it as winning and add to queue
// at end of bfs check and see if there exists a position i for police such that for all j for robber
// it is winning
// if not, return -1 else return 1
// 4. for each winning move, keep track of where it should be headed, i.e. create an array
// arr[i][j] given police at i, robber at j, police move, then in the reverse graph step, put the origional vertex as
// arr[i][j] where i is where police is at reverse_graph neighbour, j is where robber is at in rgn, p == arr[i][j] is police in graph
}
int nextMove(int R)
{
int temp = police_current;
police_current = arr[police_current][R];
debug(temp, R, police_current);
return police_current;
}
