Submission #706737

#	Time	Username	Problem	Language	Result	Execution time	Memory
706737		DennisTran	Robots (APIO13_robots)	C++17	100 / 100	871 ms	146920 KiB

robots

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define ii pair <int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 505;
const int INF = 250000;

int N, W, H, dp[MAXN][MAXN][10][10];
char a[MAXN][MAXN];
vector <ii> q[INF + 1];
ii end_pos[MAXN][MAXN][4];

inline bool inside(int x, int y) {
    return (x > 0 && y > 0 && x <= H && y <= W && a[x][y] != 'x');
}

void Find_ending_points(void) {
    FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x') {
        REP(k, 4) {
            ii pos = {i, j};
            int d = (k + (a[i][j] == 'A') * 3 + (a[i][j] == 'C')) % 4;
 
            while (true) {
                if (d == 0) {
                    if (inside(pos.first - 1, pos.second)) pos.first--;
                    else break;
                } else if (d == 1) {
                    if (inside(pos.first, pos.second + 1)) pos.second++;
                    else break;
                } else if (d == 2) {
                    if (inside(pos.first + 1, pos.second)) pos.first++;
                    else break;
                } else {
                    if (inside(pos.first, pos.second - 1)) pos.second--;
                    else break;
                }
 
                if (~end_pos[pos.first][pos.second][d].first) {
                    pos = end_pos[pos.first][pos.second][d];
                    break;
                }
 
                if (a[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (a[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }
 
            end_pos[i][j][k] = pos;
        }
    }
}

void solve(void) {
    memset(dp, 0x3f3f3f3f, sizeof dp);
    cin >> N >> W >> H;
    FOR(i, 1, H) FOR(j, 1, W) {
        cin >> a[i][j];
        if (a[i][j] >= '0' && a[i][j] <= '9') {
            dp[i][j][a[i][j] - '0'][a[i][j] - '0'] = 0;
        }
        REP(k, 4) end_pos[i][j][k] = {-1, -1};
    }
    Find_ending_points();


    REP(div, N) {
        FOR(l, 1, N - div) {
            int r = l + div;
            FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x')
                for (int k = l; k < r; k++)
                    dp[i][j][l][r] = min(dp[i][j][l][r], dp[i][j][l][k]
                        + dp[i][j][k + 1][r]);
        }

        FOR(l, 1, N - div) {
            int r = l + div;
            FOR(i, 1, H) FOR(j, 1, W) if (a[i][j] != 'x' && dp[i][j][l][r] <= INF)
                q[dp[i][j][l][r]].emplace_back(i, j);

            FOR(i, 0, INF) if (q[i].size()) {
                for (auto tmp : q[i]) {
                    int x = tmp.fi, y = tmp.se;
                    if (dp[x][y][l][r] == i) {
                        REP(k, 4) {
                            int u = end_pos[x][y][k].first, v = end_pos[x][y][k].second;
                            if (dp[u][v][l][r] > dp[x][y][l][r] + 1) {
                                dp[u][v][l][r] = dp[x][y][l][r] + 1;
                                q[dp[u][v][l][r]].emplace_back(u, v);
                            }
                        }
                    }
                }
                q[i].clear();
            }
        }
    }

    int ans = INT_MAX;
    FOR(i, 1, H) FOR(j, 1, W) ans = min(ans, dp[i][j][1][N]);
    if (ans > INF) ans = -1;
    cout << ans;
}

signed main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //int T; cin >> T; while (T--)  
    solve();
    cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}

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