Submission #623238

# Submission time Handle Problem Language Result Execution time Memory
623238 2022-08-05T11:06:11 Z jhwest2 Robots (APIO13_robots) C++17
0 / 100
1 ms 2260 KB
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { -1, 0, 1, 0 };
const int INF = 0x3f3f3f3f;

int n, w, h, go[1515151], ho[1515151], a[1515151];
int dist[505][505], dp[9][9][505][505], g[505][505];
string S[505];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> w >> h;
    for (int i = 0; i < h; i++) {
        cin >> S[i];
    }
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        int x = w * i + j;
        int y[4] = {};
        for (int k = 0; k < 4; k++) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 || nj < 0 || ni >= h || nj >= w || S[ni][nj] == '#') {
                y[k] = -1;
            }
            else y[k] = w * ni + nj;
        }
        go[5 * x] = 5 * x;
        for (int k = 0; k < 4; k++) {
            if (S[i][j] == 'A') {
                if (y[(k + 1) % 4] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[(k + 1) % 4] + 1 + (k + 1) % 4;
            }
            else if (S[i][j] == 'C') {
                if (y[(k + 3) % 4] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[(k + 3) % 4] + 1 + (k + 3) % 4;
            }
            else if (S[i][j] != '#') {
                if (y[k] == -1) {
                    go[5 * x + 1 + k] = 5 * x;
                }
                else go[5 * x + 1 + k] = 5 * y[k] + 1 + k;
            }
        }
    }
    for (int k = 0; k < 30; k++) {
        for (int i = 0; i < 5 * w * h; i++) {
            ho[i] = go[go[i]];
        }
        for (int i = 0; i < 5 * w * h; i++) {
            go[i] = ho[i];
        }
    }
    if (n == 2) {
        queue<pair<int, int>> Q, R;
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            if (S[x][y] == '1') Q.emplace(0, w * x + y);
            if (S[x][y] == '2') R.emplace(0, w * x + y);
        }
        memset(dist, 0x3f, sizeof dist);
        while (!Q.empty()) {
            auto [d, v] = Q.front(); Q.pop();
            if (dist[v / w][v % w] != INF) continue;
            dist[v / w][v % w] = d;

            for (int i = 1; i <= 4; i++) {
                Q.emplace(d + 1, go[5 * v + i] / 5);
            }
        }
        memset(g, 0x3f, sizeof g);
        while (!R.empty()) {
            auto [d, v] = R.front(); R.pop();
            if (g[v / w][v % w] != INF) continue;
            g[v / w][v % w] = d;

            for (int i = 1; i <= 4; i++) {
                R.emplace(d + 1, go[5 * v + i] / 5);
            }
        }
        int ans = INF;
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            ans = min(ans, dist[x][y] + g[x][y]);
        }
        cout << (ans == INF ? -1 : ans) << '\n';
        return 0;




    }

    iota(a, a + w * h, 0);
    for (int d = 0; d < n; d++) for (int i = 0; i < n - d; i++) {
        int j = i + d;
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            g[x][y] = INF;
            if (d == 0) {
                g[x][y] = (S[x][y] - '1' == i) ? 0 : INF;
            }
            else {
                for (int k = i; k < j; k++) {
                    g[x][y] = min(g[x][y], dp[i][k][x][y] + dp[k + 1][j][x][y]);
                }
            }
        }
        memset(dist, 0x3f, sizeof dist);
        sort(a, a + w * h, [&](int i, int j) {
            return g[i / w][i % w] < g[j / w][j % w];
            });
        queue<pair<int, int>> Q, R;
        for (int i = 0; i < w * h; i++) {
            if (g[a[i] / w][a[i] % w] != INF) {
                Q.emplace(5 * a[i], g[a[i] / w][a[i] % w]);
            }
            else break;
        }
        while (!Q.empty() || !R.empty()) {
            int v, d;
            if (Q.empty() || (!R.empty() && Q.front().second >= R.front().second)) {
                tie(v, d) = R.front(); R.pop();
            }
            else {
                tie(v, d) = Q.front(); Q.pop();
            }
            // cout << i << ' ' << j << ' ' << "(" << (v / 5 / w) << ", " << (v / 5 % w) << ") " << ' ' << d << '\n';
            assert(v % 5 == 0);

            if (dist[v / 5 / w][v / 5 % w] != INF) continue;
            dist[v / 5 / w][v / 5 % w] = d;

            for (int k = 1; k <= 4; k++) {
                if (go[v + k] % 5 != 0) continue;
                R.emplace(go[v + k], d + 1);
            }
        }
        for (int x = 0; x < h; x++) for (int y = 0; y < w; y++) {
            dp[i][j][x][y] = dist[x][y];
        }
    }
    int ans = INF;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        ans = min(ans, dp[0][n - 1][i][j]);
    }
    cout << (ans == INF ? -1 : ans);
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Incorrect 1 ms 2260 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Incorrect 1 ms 2260 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Incorrect 1 ms 2260 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Incorrect 1 ms 2260 KB Output isn't correct
3 Halted 0 ms 0 KB -