#include "coprobber.h"
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int cop, robber;
int type;
Node(int c, int r, int 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 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, 0));
}
}
}
for(int i = 0; i < n; i ++) // for every cop pos
{
for(int j = 0; j < n; j ++) // for every r pos
{
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);
}
}
}
}
//bfs
while(!q.empty())
{
Node cur = q.front();
q.pop();
for(auto v : reverse_graph[cur.cop][cur.robber][cur.type])
{
// if this neighbour is already visited and winnable, dont consider it
if(can_win[v.cop][v.robber][v.type] == true)
{
continue;
}
// if prev state was a cop move state and cop has agency to get to this state
if(v.type == 0)
{
can_win[v.cop][v.robber][v.type] = true;
arr[v.cop][v.robber] = cur.cop;
q.push(v);
}
else // previous state was a robber move first, - deg
{
deg[v.cop][v.robber] --;
if(deg == 0)
{
can_win[v.cop][v.robber][v.type] = true;
q.push(v);
}
}
}
}
// determine answer and output
int valid = true;
for(int j = 0; j < n; j ++)
{
if(!can_win[0][j][0])
{
valid = false;
break;
}
}
if(valid)
{
return 0;
}
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)
{
return 0;
}
