#include <bits/stdc++.h>
#include "coprobber.h"
using namespace std;
#define pb push_back
pair<int,int> dp[MAX_N][MAX_N][2];
vector<vector<int> > graf(MAX_N);
int visited[MAX_N][MAX_N][2];
int calc(int cop,int robber,int move)
{
if(visited[cop][robber][move]==2)
return dp[cop][robber][move].first;
//printf("Racunam %i %i %i\n",cop,robber,move);
visited[cop][robber][move]=1;
if(move==0)
{
if(visited[cop][robber][1]==0||visited[cop][robber][1]==2)
{
int d=calc(cop,robber,1);
if(d!=-1)
{
d++;
if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first>d)
dp[cop][robber][move]=make_pair(d,cop);
}
}
for(auto p:graf[cop])
{
if(visited[p][robber][1]==1)
continue;
int d=calc(p,robber,1);
if(d==-2)
continue;
d++;
if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first>d)
dp[cop][robber][move]=make_pair(d,p);
}
}
else
{
for(auto p:graf[robber])
{
if(visited[cop][p][0]==1)
{
dp[cop][robber][move]=make_pair(-2,-1);
break;
}
int d=calc(cop,p,0);
if(d==-2)
{
dp[cop][robber][move]=make_pair(-2,-1);
break;
}
d++;
if(dp[cop][robber][move].first==-1||dp[cop][robber][move].first<d)
dp[cop][robber][move]=make_pair(d,p);
}
}
if(dp[cop][robber][move].first==-1)
{
dp[cop][robber][move]=make_pair(-2,-1);
}
visited[cop][robber][move]=2;
//printf("Za %i %i %i vracam %i %i\n",cop,robber,move,dp[cop][robber][move].first,dp[cop][robber][move].second);
return dp[cop][robber][move].first;
}
int pozicija;
int start(int N, bool A[MAX_N][MAX_N])
{
for(int i=0;i<MAX_N;i++)
for(int j=0;j<MAX_N;j++)
for(int k=0;k<2;k++)
if(i==j)
dp[i][j][k]={0,-1},visited[i][j][k]=2;
else
dp[i][j][k]={-1,-1},visited[i][j][k]=0;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(A[i][j])
graf[i].pb(j);
int minn=INT_MAX,pos=-1;
for(int i=0;i<N;i++)
{
int maxx=0;
for(int j=0;j<N;j++)
{
int d=calc(i,j,0);
if(d==-2)
maxx=-2;
if(maxx!=-2)
maxx=max(maxx,d);
}
if(maxx!=-2)
{
if(maxx<minn)
{
maxx=minn;
pos=i;
}
}
}
pozicija=pos;
return pos;
}
int nextMove(int R)
{
calc(pozicija,R,0);
return pozicija=dp[pozicija][R][0].second;
}
