| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 968235 | ShauryaTheShep | Robots (APIO13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
struct State {
int x1, y1, x2, y2, moves;
};
int simulateMove(int x, int y, int direction) {
while (is_inside(x + dx[direction], y + dy[direction]) && grid[x + dx[direction]][y + dy[direction]] != 'x') {
x += dx[direction];
y += dy[direction];
}
return {x, y};
}
int bfs(pair<int, int> start1, pair<int, int> start2) {
queue<State> q;
set<tuple<int, int, int, int>> visited;
q.push({start1.first, start1.second, start2.first, start2.second, 0});
visited.insert({start1.first, start1.second, start2.first, start2.second});
while (!q.empty()) {
auto [x1, y1, x2, y2, moves] = q.front(); q.pop();
if (x1 == x2 && y1 == y2) return moves;
// Generate all possible moves for both robots
for (int dir = 0; dir < 4; dir++) {
auto [nx1, ny1] = simulateMove(x1, y1, dir);
if (visited.insert({nx1, ny1, x2, y2}).second) {
q.push({nx1, ny1, x2, y2, moves + 1});
}
auto [nx2, ny2] = simulateMove(x2, y2, dir);
if (visited.insert({x1, y1, nx2, ny2}).second) {
q.push({x1, y1, nx2, ny2, moves + 1});
}
}
}
return -1;
}