| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1225625 | duybinhbeo | Robots (APIO13_robots) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
struct Point { int r, c; };
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int R, C;
cin >> R >> C;
vector<string> grid(R);
for(int i = 0; i < R; i++) cin >> grid[i];
vector<Point> robots;
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(grid[i][j] >= '1' && grid[i][j] <= '9'){
robots.push_back({i, j});
grid[i][j] = '.';
}
}
}
int N = robots.size();
int FULL = (1 << N) - 1;
auto encode = [&](const vector<Point>& pos){
int mask = 0;
for(int i = 0; i < N; i++){
mask |= (pos[i].r * C + pos[i].c) << (i * 8);
}
return mask;
};
auto decode = [&](int code, vector<Point>& pos){
pos.resize(N);
for(int i = 0; i < N; i++){
int cell = (code >> (i * 8)) & 0xFF;
pos[i].r = cell / C;
pos[i].c = cell % C;
}
};
queue<int> Q;
unordered_map<int,int> dist;
int init = encode(robots);
Q.push(init);
dist[init] = 0;
vector<Point> pos(N);
vector<int> parent(N), group_id(N);
auto findp = [&](auto self, int x){
return parent[x] == x ? x : parent[x] = self(self, parent[x]);
};
while(!Q.empty()){
int code = Q.front(); Q.pop();
int d = dist[code];
decode(code, pos);
bool same = true;
for(int i = 1; i < N; i++){
if(pos[i].r != pos[0].r || pos[i].c != pos[0].c){
same = false;
break;
}
}
if(same){
cout << d << "\n";
return 0;
}
iota(parent.begin(), parent.end(), 0);
for(int i = 0; i < N; i++)
for(int j = i+1; j < N; j++)
if(pos[i].r == pos[j].r && pos[i].c == pos[j].c)
parent[findp(findp, i)] = findp(findp, j);
unordered_map<int, vector<int>> groups;
for(int i = 0; i < N; i++){
int g = findp(findp, i);
groups[g].push_back(i);
}
for(auto &kv : groups){
auto &g = kv.second;
for(int dir = 0; dir < 4; dir++){
vector<Point> newpos = pos;
for(int idx : g){
int rr = pos[idx].r, cc = pos[idx].c, dd = dir;
while(true){
int nr = rr + dr[dd], nc = cc + dc[dd];
if(nr < 0 || nr >= R || nc < 0 || nc >= C) break;
char cell = grid[nr][nc];
if(cell == 'x') break;
rr = nr; cc = nc;
if(cell == 'A') dd = (dd + 3) % 4;
else if(cell == 'C') dd = (dd + 1) % 4;
}
newpos[idx] = {rr, cc};
}
iota(parent.begin(), parent.end(), 0);
for(int i = 0; i < N; i++)
for(int j = i+1; j < N; j++)
if(newpos[i].r == newpos[j].r && newpos[i].c == newpos[j].c)
parent[findp(findp, i)] = findp(findp, j);
int newcode = encode(newpos);
if(!dist.count(newcode)){
dist[newcode] = d + 1;
Q.push(newcode);
}
}
}
}
cout << "-1\n";
return 0;
}