Submission #1143701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143701		Sang	Robots (APIO13_robots)	C++20	100 / 100	968 ms	60968 KiB

robots

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

int w, h, n, c[505][505], dist[10][10][505][505], vis[505][505][4];
ii a[15];
ii nxt[505][505][4];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

ii dfs(int i, int j, int d){

    if (vis[i][j][d] == 1) return {-1, -1};
    if (vis[i][j][d] == 2) return nxt[i][j][d];
    int d2 = d;
    if (c[i][j] == 2) d2 = (d - 1 + 4)%4;
    if (c[i][j] == 3) d2 = (d + 1)%4;
    vis[i][j][d] = 1;
    int x = i + dx[d2], y = j + dy[d2];
    if (x < 1 || x > w || y < 1 || y > h || c[x][y] == 1) {
        vis[i][j][d] = 2;
        return nxt[i][j][d] = {i, j};
    }
    nxt[i][j][d] = dfs(x, y, d2);
    vis[i][j][d] = 2;
    return nxt[i][j][d];
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n >> w >> h;
    swap(w, h);
    FOR (i, 1, w) FOR (j, 1, h){
        char ch; cin >> ch;
        c[i][j] = ch == 'x';
        if (ch == 'A') c[i][j] = 2;
        if (ch == 'C') c[i][j] = 3;
        if (ch >= '1' && ch <= '9') a[ch - '0'] = {i, j};
    }
    FOR (i, 1, w) {
        FOR (j, 1, h) {
            FOR (d, 0, 3){
                if (!vis[i][j][d]){
                    dfs(i, j, d);
                }
                //cout << nxt[i][j][d].fi << ' ' << nxt[i][j][d].se << '\n';
            }
        }
    }

    FOR (i, 1, n) FOR (j, i, n) FOR (x, 1, w) FOR (y, 1, h) dist[i][j][x][y] = 1e9;
    FOR (i, 1, n){
        dist[i][i][a[i].fi][a[i].se] = 0;
    }
    FOR (i, 1, n){
        FORD(j, i, 1){
            FOR (k, j, i-1) {
                FOR (x, 1, w) FOR (y, 1, h) dist[j][i][x][y] = min(dist[j][i][x][y], dist[j][k][x][y] + dist[k+1][i][x][y]);
            }
            priority_queue<pii, vector<pii>, greater<pii>> q;
            FOR (x, 1, w) FOR (y, 1, h) if (dist[j][i][x][y] != 1e9) q.push({dist[j][i][x][y], {x, y}});
            while (!q.empty()){
                int w = q.top().fi;
                int u = q.top().se.fi, v = q.top().se.se; q.pop();
                if (w != dist[j][i][u][v]) continue;
                FOR (d, 0, 3){
                    if (nxt[u][v][d].fi == -1) continue;
                    int x = nxt[u][v][d].fi, y = nxt[u][v][d].se;
                    if (dist[j][i][x][y] > w + 1){
                        dist[j][i][x][y] = w + 1;
                        q.push({w+1, {x, y}});
                    }
                }
            }
        }
    }
    int ans = 1e9;
    FOR (i, 1, w) FOR (j, 1, h) ans = min(ans, dist[1][n][i][j]);
    cout << (ans == 1e9 ? -1 : ans);
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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