| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1053396 | Zbyszek99 | 경찰관과 강도 (BOI14_coprobber) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "coprobber.h"
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define pii pair<int,int>
#define pb push_back
using namespace std;
struct dp
{
int f,s,move;
};
// DP[police][robber][turn]
bool DP[MAX_N][MAX_N][2];
int zlicz[MAX_N][MAX_N];
int where_go[MAX_N][MAX_N];
vector<int> graf[MAX_N];
int n;
int cur_poz;
int start(int N, bool A[MAX_N][MAX_N])
{
n = N;
queue<dp> winning_pos;
rep(i,0,n-1)
{
rep(j,0,n-1)
{
if(A[i][j] == 1)
{
graf[i].push_back(j);
}
}
}
rep(i,0,n-1)
{
winning_pos.push({i,i,0});
winning_pos.push({i,i,1});
zlicz[i][i] = 0;
}
rep(pocz,0,n-1)
{
rep(kon,0,n-1)
{
zlicz[pocz][kon] = (int)graf[kon].size();
}
}
while(!winning_pos.empty())
{
dp t = winning_pos.front();
winning_pos.pop();
int p = t.f;
int k = t.s;
if(t.move == 0)
{
rep(new_v,0,n-1)
{
if(A[new_v][k])
{
zlicz[p][new_v]--;
if (zlicz[p][new_v] == 0 && !DP[p][new_v][1])
{
DP[p][new_v][1] = true;
winning_pos.push({p,new_v,1});
}
}
}
}
else
{
if(!DP[p][k][0])
{
where_go[p][k] = p;
DP[p][k][0] = true;
winning_pos.push({p,k,0});
}
rep(new_v,0,n-1)
{
if(A[new_v][p] && !DP[new_v][k][0])
{
where_go[new_v][k] = p;
DP[new_v][k][0] = true;
winning_pos.push({new_v,k,0});
}
}
}
}
rep(start,0,n-1)
{
bool is = true;
rep(end,0,n-1)
{
if(DP[start][end][0] == false)
{
// cout << start << " " << end << " se\n";
is = false;
break;
}
}
if(is)
{
cur_poz = start;
return start;
}
}
return -1;
}
int nextMove(int R)
{
cur_poz = where_go[cur_poz][R];
return cur_poz;
}
int main()
{
int n;
cin >> n;
bool A[500][500];
rep(i,0,n-1)
{
rep(j,0,n-1)
{
cin >> A[i][j];
}
}
int poz = start(n,A);
cout << "police: " << poz << "\n";
if(poz == -1)
{
return 0;
}
cout << "Rob poz: ";
int rob;
cin >> rob;
while(poz != rob)
{
poz = nextMove(rob);
cout << "new poz: " << poz << "\n";
cout << "Rob: ";
cin >> rob;
}
}