#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include "coprobber.h"
#endif
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#endif
struct wow {
int cop,robber,turn;
};
vector<vector<int>> g;
const int nmax = 505;
#ifdef LOCAL
const int MAX_N = 500;
#endif
int dp[nmax][nmax][2],nrAdjacent[nmax][nmax],copPosition,situation[nmax];
int start(int n, bool a[MAX_N][MAX_N]) {
queue<wow> q;
g.resize(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
g[i].push_back(j);
}
}
}
///dp[i][j][turn], turn = 0 -> cops turn, 1->robber's turn
///dp is 1 if from this position cop can catch robber, 0 otherwise
///if it's 1 and turn = 0, then move[i][j] should contain a possible move for the cop
///that he can make so he can get to the robber.
for (int i = 0; i < n; i++) {
dp[i][i][0] = dp[i][i][1] = 1;
q.push({i,i,0});
q.push({i,i,1});
}
///queue just contains values that have been turned to 1
while(!q.empty()) {
int cop = q.front().cop;
int robber = q.front().robber;
int turn = q.front().turn;
q.pop();
auto change = [&](int cop, int robber, int turn) {
if (dp[cop][robber][turn] == 0) {
dp[cop][robber][turn] = 1;
}
q.push({cop,robber,turn});
};
if (turn == 1) { // robber's turn, this leads to the samae position in 0, as well as all neighbours of the cop in 0.
for (auto k : g[cop]) {
change(k,robber,0);
}
change(cop,robber,0);///cop can wait and get lead to this situation.
} else {
///any neighbours 1's need to have all of their robber neighbours taken
///we take a robber move from a certain neighbour to get here
for (auto k : g[robber]) {
nrAdjacent[cop][k]++;///nr of adjacent cop move nodes that are 1 next to this robber move
if (nrAdjacent[cop][k] == g[k].size()) {
change(cop, k, 1);///this robber turn position is taken
}
}
}
}
///we want to find a corner where all dp[A][x][0] = 1
for (int i = 0; i < n; i++) {
bool any0 = false;
for (int j = 0; j < n; j++) {
if (dp[i][j][0] == 0) {
any0 = true;
break;
}
}
if (!any0) {
copPosition = i;
return i;
}
}
return -1;
}
int nextMove(int R) {
return -1;
situation[copPosition]++;
for (auto nextCop : g[copPosition]) {
if (dp[nextCop][R][1] == 1 && situation[nextCop] == 0) { /// it will be the robber's turn after this move
return nextCop;
}
}
// if (dp[copPosition] == 1) {
// }
return -1;
}
#ifdef LOCAL
bool a[MAX_N][MAX_N];
int main() {
int n;
in >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
in >> a[i][j];
}
}
start(n , a);
}
#endif
Compilation message
coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:69:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | if (nrAdjacent[cop][k] == g[k].size()) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
328 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
328 KB |
nextMove() returned a value that is either outside 0..N-1 or the new cop position is not a neighbour to the previous one |
| 2 |
Halted |
0 ms |
0 KB |
- |
