| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 968235 | ShauryaTheShep | 로봇 (APIO13_robots) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
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;
}