Submission #1165680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165680		Muhammet	Robots (APIO13_robots)	C++20	0 / 100	2 ms	4164 KiB

robots

#include "bits/stdc++.h"

using namespace std;

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

const int N = 305;

char a[N][N];

int mp[N][N], n, w, h, ind[10], nd, dpfn[10][10][10005];

map <pair <int,int>, int> ds;

pair <int, int> dp[N][N][4];

vector <int> dis;

vector <vector <int>> v;

pair <int, int> f(int i, int j, int x) {
    if(dp[i][j][x] != pair <int, int> {0, 0}) return dp[i][j][x];
    int x1 = (x % 2 ? 0 : (!x ? -1 : 1)), y1 = (!(x % 2) ? 0 : (x == 1 ? 1 : -1));
    if(a[i + x1][j + y1] != 'x' and i + x1 <= h and i + x1 > 0 and j + y1 <= w and j + y1 > 0) {
        int xx = x, i1 = i, j1 = j;
        i += x1, j += y1;
        if(a[i][j] == 'C') {
            x++;
            if(x == 4) x = 0;
        }
        if(a[i][j] == 'A') {
            x--;
            if(x == -1) x = 3;
        }
        return dp[i1][j1][xx] = f(i, j, x);
    }
    return dp[i][j][x] = pair <int, int> {i, j};
}

int fn(int a, int b, int vn) {
    if(dpfn[a][b][vn] != -1) return dpfn[a][b][vn];
    queue <int> q;
    dis.assign(nd+1, 1e9);
    q.push(vn);
    dis[vn] = 0;
    for(int i = 1; i <= nd; i++) {
        ds[{vn, i}] = 1e9;
    }
    ds[{vn, vn}] = 0;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(auto i : v[x]) {
            if(dis[i] > dis[x] + 1) {
                dis[i] = dis[x] + 1;
                ds[{vn, i}] = dis[i];
                q.push(i);
            }
        }
    }
    if(a == b) return dpfn[a][b][vn] = dis[ind[a]];
    int ans = 1e9;
    for(int i = a; i < b; i++) {
        int x = 1e9;
        for(int v1 = 1; v1 <= nd; v1++) {
            x = min(x, fn(a, i, v1) + ds[{v1, vn}]);
        }
        int y = 1e9;
        for(int v1 = 1; v1 <= nd; v1++) {
            y = min(y, fn(i+1, b, v1) + ds[{v1, vn}]);
        }
        ans = min(ans, x + y);
    }
    // cout << a << ' ' << b << ' ' << vn << ' ' << ans << "\n";
    return dpfn[a][b][vn] = ans;
}

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

    cin >> n >> w >> h;

    memset(dpfn, -1, sizeof dpfn);
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            cin >> a[i][j];
            mp[i][j] = ++nd;
            if(a[i][j] >= '1' and a[i][j] <= '9') ind[a[i][j] - '0'] = nd;
        }
    }

    v.resize(nd+1);
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++) {
            for(int k = 0; k < 4; k++) {
                pair <int, int> ind = f(i, j, k);
                if(ind != pair <int, int> {i, j}) v[mp[i][j]].push_back(mp[ind.ff][ind.ss]);
            }
        }
    }

    int ans = 1e9;
    for(int i = 1; i <= nd; i++) {
        ans = min(ans, fn(1, n, i));
    }

    cout << (ans == 1e9 ? -1 : ans);

    return 0;
}

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