Submission #1165151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165151		Muhammet	Robots (APIO13_robots)	C++20	30 / 100	28 ms	5704 KiB

robots

#include "bits/stdc++.h"

using namespace std;

#define ff first
#define ss second
#define ll long long

const int N = 505;

char a[N][N];

int b[10][N][N], n, w, h;

struct ab {
    int x, y, k;
};

pair <int, int> f1(int i, int j, int x1, int y1) {
    while(a[i + x1][j + y1] != 'x' and i + x1 <= h and i + x1 > 0 and j + y1 <= w and j + y1 > 0) {
        i += x1, j += y1;
        if(a[i][j] == 'C') {
        	if(x1 == -1 and y1 == 0) x1 = 0, y1 = 1;
        	else if(x1 == 0 and y1 == 1) x1 = 1, y1 = 0;
        	else if(x1 == 1 and y1 == 0) x1 = 0, y1 = -1;
        	else if(x1 == 0 and y1 == -1) x1 = -1, y1 = 0;
        }
        if(a[i][j] == 'A') {
        	if(x1 == -1 and y1 == 0) x1 = 0, y1 = -1;
        	else if(x1 == 0 and y1 == 1) x1 = -1, y1 = 0;
        	else if(x1 == 1 and y1 == 0) x1 = 0, y1 = 1;
        	else if(x1 == 0 and y1 == -1) x1 = 1, y1 = 0;
        }
    }
    return {i, j};
}

void f(int c, int i, int j) {
    queue <ab> q;
    ab abb;
    abb.x = i, abb.y = j, abb.k = 0;
    b[c][i][j] = 0;
    q.push(abb);
    while(!q.empty()) {
        ab z = q.front();
        q.pop();
        if(b[c][z.x][z.y] != z.k) continue;
        pair <int, int> ind = f1(z.x, z.y, 1, 0);
        if(b[c][ind.ff][ind.ss] > z.k + 1){
            abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
            b[c][ind.ff][ind.ss] = z.k+1;
            q.push(abb);
        }
        ind = f1(z.x, z.y, 0, 1);
        if(b[c][ind.ff][ind.ss] > z.k + 1){
            abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
            b[c][ind.ff][ind.ss] = z.k+1;
            q.push(abb);
        }
        ind = f1(z.x, z.y, -1, 0);
        if(b[c][ind.ff][ind.ss] > z.k + 1){
            abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
            b[c][ind.ff][ind.ss] = z.k+1;
            q.push(abb);
        }
        ind = f1(z.x, z.y, 0, -1);
        if(b[c][ind.ff][ind.ss] > z.k + 1){
            abb.x = ind.ff, abb.y = ind.ss, abb.k = z.k+1;
            b[c][ind.ff][ind.ss] = z.k+1;
            q.push(abb);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> w >> h;

    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            cin >> a[i][j];
            for(int ij = 1; ij <= n; ij++) {
            	b[ij][i][j] = 1e9;
            }
        }
    }

    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            if(a[i][j] >= '1' and a[i][j] <= '9') {
            	f((a[i][j] - '0'), i, j);
            }
        }
    }

    ll ans = 0;

    for(int o = 1; o < n; o++) {
    	ll oo = 1e9;
    	pair <int, int> bb, in;
    	for(int x1 = 1; x1 < n; x1++) {
    		for(int x2 = x1+1; x2 <= n; x2++) {
    			for(int i = 1; i <= h; i++) {
    				for(int j = 1; j <= w; j++) {
    					if(oo > b[x1][i][j] + b[x2][i][j]) {
    						oo = b[x1][i][j] + b[x2][i][j];
    						bb = {x1, x2};
    						in = {i, j};
    					}
    				}
    			}
    		}
    	}
    	if(oo == 1e9) {
    		cout << -1;
    		return 0;
    	}
    	ans += oo;
    	for(int i = 1; i <= h; i++) {
    		for(int j = 1; j <= w; j++) {
    			b[bb.ff][i][j] = 1e9;
    			b[bb.ss][i][j] = 1e9;
    		}
    	}
    	f(bb.ff, in.ff, in.ss);
    }

    cout << ans;

    return 0;
}

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