| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1211634 | minh30082008 | Robots (APIO13_robots) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct Robot {
int minLabel, maxLabel;
int x, y;
};
struct State {
vector<Robot> robots;
int pushes;
// Sort state to avoid duplicates due to permutation of robot vector
bool operator<(const State& other) const {
auto a = robots, b = other.robots;
sort(a.begin(), a.end(), [](Robot r1, Robot r2) {
return r1.minLabel < r2.minLabel;
});
sort(b.begin(), b.end(), [](Robot r1, Robot r2) {
return r1.minLabel < r2.minLabel;
});
return a < b;
}
};
// Directions: up, right, down, left
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
int w, h, n;
vector<string> grid;
// Kiểm tra hợp lệ vị trí
bool is_valid(int x, int y) {
return x >= 0 && y >= 0 && x < h && y < w && grid[x][y] != 'x';
}
// Xoay hướng
int rotate_dir(int dir, char plate) {
return plate == 'A' ? (dir + 3) % 4 : (dir + 1) % 4; // A: left, C: right
}
// Tạo hash cho trạng thái robot
string encode_state(const vector<Robot>& robots) {
vector<string> s;
for (auto& r : robots) {
s.push_back(to_string(r.minLabel) + "-" + to_string(r.maxLabel) + "@" + to_string(r.x) + "," + to_string(r.y));
}
sort(s.begin(), s.end());
string res;
for (auto& e : s) res += e + "|";
return res;
}
// Tìm robot cùng vị trí có thể hợp nhất
void merge(vector<Robot>& robots) {
map<pair<int, int>, vector<int>> pos;
for (int i = 0; i < robots.size(); i++) {
pos[{robots[i].x, robots[i].y}].push_back(i);
}
bool changed = true;
while (changed) {
changed = false;
for (auto& [p, idxs] : pos) {
vector<int> new_idxs;
for (int i = 0; i < idxs.size(); ++i) {
for (int j = i + 1; j < idxs.size(); ++j) {
auto& r1 = robots[idxs[i]];
auto& r2 = robots[idxs[j]];
if (abs(r1.minLabel - r2.maxLabel) == 1 || abs(r2.minLabel - r1.maxLabel) == 1 ||
abs(r1.maxLabel - r2.minLabel) == 1 || abs(r2.maxLabel - r1.minLabel) == 1) {
// Merge
Robot merged = {
min(r1.minLabel, r2.minLabel),
max(r1.maxLabel, r2.maxLabel),
r1.x, r1.y
};
robots.erase(robots.begin() + idxs[j]);
robots.erase(robots.begin() + idxs[i]);
robots.push_back(merged);
changed = true;
break;
}
}
if (changed) break;
}
if (changed) break;
}
pos.clear();
for (int i = 0; i < robots.size(); i++) {
pos[{robots[i].x, robots[i].y}].push_back(i);
}
}
}
int bfs(vector<Robot> start) {
queue<State> q;
set<string> visited;
q.push({start, 0});
visited.insert(encode_state(start));
while (!q.empty()) {
State cur = q.front(); q.pop();
if (cur.robots.size() == 1 && cur.robots[0].minLabel == 1 && cur.robots[0].maxLabel == n) {
return cur.pushes;
}
for (int i = 0; i < cur.robots.size(); ++i) {
for (int d = 0; d < 4; ++d) {
Robot r = cur.robots[i];
int dir = d;
// Nếu đứng trên plate xoay thì xoay trước
if (grid[r.x][r.y] == 'A' || grid[r.x][r.y] == 'C') {
dir = rotate_dir(dir, grid[r.x][r.y]);
}
int nx = r.x + dx[dir], ny = r.y + dy[dir];
while (is_valid(nx, ny)) {
// Nếu gặp plate xoay khi di chuyển
if (grid[nx][ny] == 'A' || grid[nx][ny] == 'C') {
dir = rotate_dir(dir, grid[nx][ny]);
}
int tx = nx + dx[dir], ty = ny + dy[dir];
if (!is_valid(tx, ty)) break;
nx = tx;
ny = ty;
}
vector<Robot> next = cur.robots;
next[i].x = nx;
next[i].y = ny;
merge(next);
string enc = encode_state(next);
if (!visited.count(enc)) {
visited.insert(enc);
q.push({next, cur.pushes + 1});
}
}
}
}
return -1;
}
int main() {
cin >> n >> w >> h;
grid.resize(h);
vector<Robot> robots;
for (int i = 0; i < h; ++i) {
cin >> grid[i];
for (int j = 0; j < w; ++j) {
if (isdigit(grid[i][j])) {
int label = grid[i][j] - '0';
robots.push_back({label, label, i, j});
}
}
}
cout << bfs(robots) << "\n";
return 0;
}