| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 77803 | Charis02 | 경찰관과 강도 (BOI14_coprobber) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "coprobber.h"
#include<iostream>
#include<vector>
#include<queue>
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAX_N 505
#define ll long long
using namespace std;
struct state{
int who; // 0 - cop plays next, 1 rob plays next
int cop;
int rob;
};
int leftToWin[MAX_N][MAX_N][2],nextPos[MAX_N][MAX_N],curpos=0;
int start(int N, bool A[MAX_N][MAX_N])
{
rep(i,0,N)
{
int deg = 0;
rep(j,0,N)
{
if(A[i][j])
deg++;
}
rep(j,0,N)
{
if(i != j)
{
leftToWin[i][j][0] = 1;
leftToWin[i][j][1] = deg;
}
}
}
queue < state > q;
rep(i,0,N)
{
state s;
s.cop = i;
s.rob = i;
s.who = 0;
q.push(s);
s.who = 1;
q.push(s);
}
int totalstates = 0;
while(!q.empty())
{
state cur = q.front();
q.pop();
totalstates++;
// cout << cur.cop << " " << cur.rob << " " << cur.who << endl;
if(cur.who == 0)
{
rep(i,0,N)
{
if(A[i][cur.rob] && leftToWin[cur.cop][i][1] != 0)
{
leftToWin[cur.cop][i][1]--;
if(leftToWin[cur.cop][i][1] == 0)
{
state neo = cur;
neo.rob = i;
neo.who = 1;
q.push(neo);
}
}
}
}
else
{
rep(i,0,N)
{
if((A[cur.cop][i] || cur.cop == i) && leftToWin[i][cur.rob][0] != 0)
{
leftToWin[i][cur.rob][0] = 0;
state neo = cur;
neo.cop = i;
neo.who = 0;
q.push(neo);
nextPos[i][cur.rob] = cur.cop;
}
}
}
}
return totalstates == 2*N*N ? 0 : -1;
}
int nextMove(int R)
{
return curpos = nextPos[curpos][R];
}
/*
int main()
{
int n;
cin >> n;
bool a[MAX_N][MAX_N];
rep(i,0,n)
{
rep(j,0,n)
{
cin >> a[i][j];
}
}
cout<<start(n,a) << endl;
while(true)
{
int x;
cin >> x;
cout << nextMove(x) << endl;
}
}
*/