Submission #1211610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211610		Nguyenhuutam	Robots (APIO13_robots)	C++20	30 / 100	1596 ms	35732 KiB

robots

#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0}; // up, right, down, left
const int dy[4] = {0, 1, 0, -1};

int n, w, h;
vector<string> grid;

struct Robot {
    int min_label, max_label, x, y;
    bool operator<(const Robot &r) const {
        return tie(min_label, max_label, x, y) < tie(r.min_label, r.max_label, r.x, r.y);
    }
};

using State = vector<Robot>;

string hash_state(const State &s) {
    State t = s;
    sort(t.begin(), t.end());
    string res;
    for (auto r : t) {
        res += to_string(r.min_label) + "," + to_string(r.max_label) + "," + to_string(r.x) + "," + to_string(r.y) + ";";
    }
    return res;
}

bool can_merge(const Robot &a, const Robot &b) {
    return (a.max_label + 1 == b.min_label || b.max_label + 1 == a.min_label);
}

State merge_robots(State s) {
    bool changed = true;
    while (changed) {
        changed = false;
        for (int i = 0; i < s.size(); ++i) {
            for (int j = i + 1; j < s.size(); ++j) {
                if (s[i].x == s[j].x && s[i].y == s[j].y && can_merge(s[i], s[j])) {
                    Robot merged;
                    merged.min_label = min(s[i].min_label, s[j].min_label);
                    merged.max_label = max(s[i].max_label, s[j].max_label);
                    merged.x = s[i].x;
                    merged.y = s[i].y;
                    State t;
                    for (int k = 0; k < s.size(); ++k)
                        if (k != i && k != j) t.push_back(s[k]);
                    t.push_back(merged);
                    s = t;
                    changed = true;
                    goto NEXT;
                }
            }
        }
        NEXT:;
    }
    return s;
}

int bfs(State start) {
    queue<pair<State, int>> q;
    unordered_set<string> visited;

    start = merge_robots(start);
    q.push({start, 0});
    visited.insert(hash_state(start));

    while (!q.empty()) {
        auto [state, dist] = q.front(); q.pop();
        if (state.size() == 1 && state[0].min_label == 1 && state[0].max_label == n) return dist;

        for (int i = 0; i < state.size(); ++i) {
            for (int dir = 0; dir < 4; ++dir) {
                State new_state = state;
                Robot &r = new_state[i];
                int nx = r.x, ny = r.y, d = dir;

                if (grid[nx][ny] == 'A') d = (dir + 3) % 4;
                if (grid[nx][ny] == 'C') d = (dir + 1) % 4;

                while (true) {
                    int tx = nx + dx[d];
                    int ty = ny + dy[d];
                    if (tx < 0 || tx >= h || ty < 0 || ty >= w || grid[tx][ty] == 'x') break;

                    nx = tx;
                    ny = ty;

                    if (grid[nx][ny] == 'A') d = (d + 3) % 4;
                    if (grid[nx][ny] == 'C') d = (d + 1) % 4;
                }

                r.x = nx;
                r.y = ny;
                new_state = merge_robots(new_state);
                string hsh = hash_state(new_state);
                if (!visited.count(hsh)) {
                    visited.insert(hsh);
                    q.push({new_state, dist + 1});
                }
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> w >> h;
    grid.resize(h);
    for (int i = 0; i < h; ++i) cin >> grid[i];

    State start;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            if (isdigit(grid[i][j])) {
                int label = grid[i][j] - '0';
                start.push_back({label, label, i, j});
            }

    cout << bfs(start);
}

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