제출 #1221072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221072		nanaseyuzuki	Robots (APIO13_robots)	C++20	30 / 100	1593 ms	39912 KiB

robots

#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;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40