Submission #560511

#	Time	Username	Problem	Language	Result	Execution time	Memory
560511		Cyanmond	Robots (APIO13_robots)	C++17	100 / 100	1098 ms	89836 KiB

robots

#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)

constexpr int inf = 1050000000;

constexpr array<pair<int, int>, 4> dxy = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};

template <class T> bool chmin(T &a, const T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

array<pair<int, int>, 4> dest[500][500];
int dist[500][500][9][9];

int main() {
    int N, W, H;
    cin >> N >> W >> H;
    vector<string> S(H);
    for (auto &e : S) cin >> e;
    // vector<vector<array<pair<int, int>, 4>>> dest(H, vector<array<pair<int, int>, 4>>(W));
    REP(i, H) REP(j, W) REP(k, 4) dest[i][j][k] = {-2, -2};

    auto calc_dest = [&](auto &&self, const int h, const int w, const int k) -> pair<int, int> {
        if (dest[h][w][k] == make_pair(-3, -3)) return dest[h][w][k] = {-1, -1};
        if (dest[h][w][k] != make_pair(-2, -2)) return dest[h][w][k];
        const int nh = h + dxy[k].first, nw = w + dxy[k].second;
        if (nh < 0 or nw < 0 or nh >= H or nw >= W) return dest[h][w][k] = {h, w};
        if (S[nh][nw] == 'x') return dest[h][w][k] = {h, w};
        if (S[nh][nw] == 'A') {
            dest[h][w][k] = {-3, -3};
            return dest[h][w][k] = self(self, nh, nw, (k + 3) % 4);
        }
        if (S[nh][nw] == 'C') {
            dest[h][w][k] = {-3, -3};
            return dest[h][w][k] = self(self, nh, nw, (k + 1) % 4);
        }
        return dest[h][w][k] = self(self, nh, nw, k);
    };

    REP(i, H) REP(j, W) REP(k, 4) calc_dest(calc_dest, i, j, k);

    // vector dist(H, vector(W, vector(N, vector(N, inf))));
    REP(i, H) REP(j, W) REP(l, N) REP(r, N) dist[i][j][l][r] = inf;
    REP(i, H) REP(j, W) if (S[i][j] >= '1' and S[i][j] < '1' + N) {
        const int v = S[i][j] - '1';
        chmin(dist[i][j][v][v], 0);
        REP(k, 4) {
            if (dest[i][j][k] != make_pair(-1, -1))
                chmin(dist[dest[i][j][k].first][dest[i][j][k].second][v][v], 1);
        }
    }

    REP(length, N) {
        REP(l, N - length) {
            const int r = l + length;
            REP(i, H) REP(j, W) {
                REP3(d, l, r) chmin(dist[i][j][l][r], dist[i][j][l][d] + dist[i][j][d + 1][r]);
            }

            deque<tuple<int,int,int>> deq;
            REP(i, H) REP(j, W) if (dist[i][j][l][r] != inf) { deq.push_back({dist[i][j][l][r], i, j}); }
            sort(deq.begin(),deq.end());
            while (not deq.empty()) {
                const auto [nc, h, w] = deq.front();
                deq.pop_front();
                if (nc > dist[h][w][l][r]) continue;
                REP(k, 4) {
                    const int nh = dest[h][w][k].first, nw = dest[h][w][k].second;
                    if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
                    if (chmin(dist[nh][nw][l][r], nc + 1)) {
                        deq.push_front({nc + 1, nh, nw});
                    }
                }
            }
        }
    }

    int ans = inf;
    REP(i, H) REP(j, W) chmin(ans, dist[i][j][0][N - 1]);
    if (ans == inf) ans = -1;
    cout << ans << endl;
}

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