Submission #1211634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211634		minh30082008	Robots (APIO13_robots)	C++17	Compilation error	0 ms	0 KiB

robots

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

Compilation message (stderr)

In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from robots.cpp:1:
/usr/include/c++/11/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = const Robot*; _Iterator2 = const Robot*]':
/usr/include/c++/11/bits/stl_algobase.h:1295:14:   required from 'bool std::__lexicographical_compare_impl(_II1, _II1, _II2, _II2, _Compare) [with _II1 = const Robot*; _II2 = const Robot*; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/11/bits/stl_algobase.h:1312:46:   required from 'static bool std::__lexicographical_compare<_BoolType>::__lc(_II1, _II1, _II2, _II2) [with _II1 = const Robot*; _II2 = const Robot*; bool _BoolType = false]'
/usr/include/c++/11/bits/stl_algobase.h:1383:60:   required from 'bool std::__lexicographical_compare_aux1(_II1, _II1, _II2, _II2) [with _II1 = const Robot*; _II2 = const Robot*]'
/usr/include/c++/11/bits/stl_algobase.h:1417:49:   required from 'bool std::__lexicographical_compare_aux(_II1, _II1, _II2, _II2) [with _II1 = __gnu_cxx::__normal_iterator<const Robot*, std::vector<Robot> >; _II2 = __gnu_cxx::__normal_iterator<const Robot*, std::vector<Robot> >]'
/usr/include/c++/11/bits/stl_algobase.h:1747:48:   required from 'bool std::lexicographical_compare(_II1, _II1, _II2, _II2) [with _II1 = __gnu_cxx::__normal_iterator<const Robot*, std::vector<Robot> >; _II2 = __gnu_cxx::__normal_iterator<const Robot*, std::vector<Robot> >]'
/usr/include/c++/11/bits/stl_vector.h:1931:42:   required from 'bool std::operator<(const std::vector<_Tp, _Alloc>&, const std::vector<_Tp, _Alloc>&) [with _Tp = Robot; _Alloc = std::allocator<Robot>]'
robots.cpp:22:20:   required from here
/usr/include/c++/11/bits/predefined_ops.h:45:23: error: no match for 'operator<' (operand types are 'const Robot' and 'const Robot')
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from robots.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:1187:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
 1187 |     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1187:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from robots.cpp:1:
/usr/include/c++/11/bits/predefined_ops.h:45:23: note:   'const Robot' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from robots.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h:1195:5: note: candidate: 'template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
 1195 |     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/11/bits/stl_iterator.h:1195:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/11/bits/stl_algobase.h:71,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from robots.cpp:1:
/usr/include/c++/11/bits/predefined_ops.h:45:23: note:   'const Robot' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
   45 |       { return *__it1 < *__it2; }
      |                ~~~~~~~^~~~~~~~