Submission #1127628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127628		Dedibeat	Robots (APIO13_robots)	C++20	30 / 100	29 ms	19524 KiB

robots

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, w, h;
tuple<int, int, int> nxt[500][500][4];
pair<int, int> stop[500][500][4];
bool vis[500][500][4];
vector<string> grid;
void compute_next();
void compute_stop();
void compute_adj();
vector<int> adj[500 * 500];
int main(){
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> w >> h;
	grid.assign(h, "");
	vector<int> robots;
	for(int i = 0; i < h; i++){
        cin >> grid[i];
        for(int j = 0; j < w; j++){
            if(grid[i][j] > '0' && grid[i][j] <= '9')
                robots.push_back(i * w + j);
        }
	}
	compute_next();
	compute_stop();
	compute_adj();

    int r1 = robots[0], r2 = robots[1];
    int N = h * w;
    vector<bool> V(N, 0);
    vector<int> cost1(N, 1e9), cost2(N, 1e9);
    queue<pair<int, int>> q;
    q.push({r1, 0});
    while(!q.empty()){
        auto [v, d] = q.front(); q.pop();
        cost1[v] = d;
        V[v] = true;
        for(auto u : adj[v]){
            if(!V[u]) q.push({u, d + 1});
        }
    }
    V.assign(N, 0);
    q.push({r2, 0});
    while(!q.empty()){
        auto [v, d] = q.front(); q.pop();
        cost2[v] = d;
        V[v] = true;
        for(auto u : adj[v]){
            if(!V[u]) q.push({u, d + 1});
        }
    }

    int ans = 1e9, mn = -1;
    for(int i = 0; i < N; i++) if(cost1[i] + cost2[i] < ans) ans = cost1[i] + cost2[i], mn = i;
    if(ans >= 1e8) cout << "-1";
    else cout << ans;
}

void compute_adj(){
    auto ind = [&](pair<int, int> pt){
        return pt.first * w + pt.second;
    };
    for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++){
        int u = ind({i, j});
        for(int turn = 0; turn < 4; turn++)
            adj[u].push_back(ind(stop[i][j][turn]));
    }
}



void compute_stop(){
    for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++)
    for(int turn = 0; turn < 4; turn++)
    {
        int x = i, y = j, t = turn;
        vector<tuple<int, int, int>> Back;
        while(true){
            auto [x1, y1, t1] = nxt[x][y][t];
            if(x1 == -1){
                stop[i][j][turn] = {x, y};
                break;
            }
            if(vis[x][y][t]){
                stop[i][j][turn] = stop[x][y][t];
                break;
            }
            Back.emplace_back(x, y, t);
            x = x1, y = y1, t = t1;
        }

        for(auto &[x1, y1, t1] : Back){
            vis[x1][y1][t1] = true;
            stop[x1][y1][t1] = stop[i][j][turn];
        }
    }


}
void compute_next(){
    for(int i = 0; i < h; i++)
    for(int j = 0; j < w; j++)
    for(int turn  = 0; turn < 4; turn++)
            nxt[i][j][turn] = {-1, -1, -1};

	for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            for(int turn = 0; turn < 4; turn++){
                auto &[x, y, t] = nxt[i][j][turn];
                if(turn == 0){
                    if(i == 0)
                        continue;
                    if(grid[i-1][j] == 'x')
                        continue;
                    x = i - 1, y = j;
                }
                if(turn == 1){
                    if(j == w - 1)
                        continue;
                    if(grid[i][j + 1] == 'x')
                        continue;
                    x = i, y = j + 1;
                }
                if(turn == 2){
                    if(i == h - 1)
                        continue;
                    if(grid[i + 1][j] == 'x')
                        continue;
                    x = i + 1, y = j;
                }
                if(turn == 3){
                    if(j == 0)
                        continue;
                    if(grid[i][j - 1] == 'x')
                        continue;
                    x = i, y = j - 1;
                }
                if(grid[x][y] == 'A') t = (turn - 1 + 4) % 4;
                else if(grid[x][y] == 'C') t = (turn + 1) % 4;
                else t = turn;
               // cout << "next:" << i << ' ' << j << ' ' << turn << '\n';
               // cout << x << ' ' << y << ' ' << t << endl;
            }


}

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