Submission #1225625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225625		duybinhbeo	Robots (APIO13_robots)	C++20	Compilation error	0 ms	0 KiB

robots

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

Compilation message (stderr)

robots.cpp: In instantiation of 'main()::<lambda(auto:47, int)> [with auto:47 = main()::<lambda(auto:47, int)>]':
robots.cpp:81:33:   required from here
robots.cpp:57:53: error: use of 'main()::<lambda(auto:47, int)> [with auto:47 = main()::<lambda(auto:47, int)>]' before deduction of 'auto'
   57 |         return parent[x] == x ? x : parent[x] = self(self, parent[x]);
      |                                                 ~~~~^~~~~~~~~~~~~~~~~