Submission #1221072

#TimeUsernameProblemLanguageResultExecution timeMemory
1221072nanaseyuzukiRobots (APIO13_robots)C++20
30 / 100
1593 ms39912 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int n, w, h; vector<string> grid; int goal_mask; // 4 hướng: up, down, left, right int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; // rotate: A = ccw, C = cw int turn_ccw[4] = {2, 3, 1, 0}; // up->left(2), down->right(3), left->down(1), right->up(0) int turn_cw [4] = {3, 2, 0, 1}; // up->right, down->left, left->up, right->down struct Robot { int mask, x, y; bool operator<(Robot const& o) const { if (mask!=o.mask) return mask<o.mask; if (x!=o.x) return x<o.x; return y<o.y; } }; // hash trạng thái thành string string hash_state(vector<Robot>& A){ sort(A.begin(), A.end()); string s; for(auto &r: A){ s += to_string(r.mask) + ":" + to_string(r.x) + "," + to_string(r.y) + ";"; } return s; } int bfs(vector<Robot> start){ unordered_set<string> vis; queue<pair<vector<Robot>,int>> q; string h0 = hash_state(start); vis.insert(h0); q.push({start, 0}); while(!q.empty()){ auto [st, pushes] = q.front(); q.pop(); // kiểm tra đã hợp nhất hết? if (st.size()==1 && st[0].mask == goal_mask) return pushes; // thử đẩy từng robot theo 4 hướng for(int i=0; i<st.size(); i++){ for(int d=0; d<4; d++){ // sao chép trạng thái vector<Robot> nxt = st; Robot cur = nxt[i]; // đánh dấu robot i bị xoá tạm nxt.erase(nxt.begin()+i); int cx = cur.x, cy = cur.y, dir = d; // di chuyển đến khi chạm vật cản while(true){ int nx = cx + dx[dir], ny = cy + dy[dir]; // nếu ra ngoài hoặc gặp 'x' -> dừng if (nx<0||nx>=h||ny<0||ny>=w|| grid[nx][ny]=='x') break; cx = nx; cy = ny; char c = grid[cx][cy]; if (c=='A') dir = turn_ccw[dir]; else if (c=='C') dir = turn_cw[dir]; } // cur dừng ở (cx, cy) cur.x = cx; cur.y = cy; // hợp nhất với bất cứ robot nào cùng ô bool merged = true; while(merged){ merged = false; for(int j=0; j<nxt.size(); j++){ if (nxt[j].x==cur.x && nxt[j].y==cur.y){ // hợp nhất cur.mask |= nxt[j].mask; nxt.erase(nxt.begin()+j); merged = true; break; } } } // thêm robot cur trở lại nxt.push_back(cur); // encode và kiểm tra visit string hs = hash_state(nxt); if (!vis.count(hs)){ vis.insert(hs); q.push({nxt, pushes+1}); } } } } return -1; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> w >> h; grid.resize(h); for(int i=0;i<h;i++) cin >> grid[i]; vector<Robot> start; goal_mask = (1<<n) - 1; // đọc vị trí robot for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ char c = grid[i][j]; if (c>='1' && c<='9'){ int id = c - '1'; // đánh số 0..n-1 start.push_back({1<<id, i, j}); // coi như ô trống để di chuyển qua grid[i][j] = '.'; } } } cout << bfs(start) << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...