oj.uz

Submission #469387

# Submission time Handle Problem Language Result Execution time Memory
469387 2021-08-31T17:52:35 Z chienyu_xiong Robots (APIO13_robots) C++17
100 / 100
 934 ms 124492 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

const int INF = 250000;

int n, h, w;
char g[500][500];
pair<int, int> end_pos[500][500][4];
int dp[500][500][9][9];
vector<pair<int, int>> q[INF];

bool inside(int x, int y) {
    return (x >= 0 && y >= 0 && x < h && y < w && g[x][y] != 'x');
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof(dp));

    FOR(i, 0, h) FOR(j, 0, w) {
        cin >> g[i][j];
        if (g[i][j] - '0' > 0 && g[i][j] - '0' < 10) {
            dp[i][j][g[i][j] - '1'][g[i][j] - '1'] = 0;
        }
    }

    // Determine final positions from each push
    FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
        FOR(k, 0, 4) {
            pair<int, int> pos = {i, j};
            int d = (k + (g[i][j] == 'A') * 3 + (g[i][j] == 'C')) % 4;  // NESW

            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 (g[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (g[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }

            end_pos[i][j][k] = pos;
        }
    }

    // Find the minimum no. of pushes to get robot k-l to block (i, j)
    FOR(rng, 0, n) {
        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                FOR(d, k, l) {
                    dp[i][j][k][l] =
                        min(dp[i][j][k][l],
                            dp[i][j][k][d] + dp[i][j][d + 1][l]);
                }
            }
        }

        FOR(k, 0, n - rng) {
            int l = k + rng;

            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x') {
                if (dp[i][j][k][l] <= INF) q[dp[i][j][k][l]].push_back({i, j});
            }
            
            FOR(i, 0, INF) {
                for (pair<int, int> pos : q[i]) {
                    int x, y;
                    tie(x, y) = pos;
                    if (dp[x][y][k][l] == i) {
                        FOR(d, 0, 4) {
                            int nx, ny;
                            tie(nx, ny) = end_pos[x][y][d];
                            if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1) {
                                q[dp[nx][ny][k][l] = dp[x][y][k][l] + 1].push_back({nx, ny});
                            }
                        }
                    }
                }
                q[i].clear();
            }
        }
    }

    int ans = INT_MAX;
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n - 1]);
    cout << (ans > INF ? -1 : ans);
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 37 ms 85364 KB Output is correct
3 Correct 38 ms 85328 KB Output is correct
4 Correct 37 ms 85444 KB Output is correct
5 Correct 37 ms 85448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 37 ms 85364 KB Output is correct
3 Correct 38 ms 85328 KB Output is correct
4 Correct 37 ms 85444 KB Output is correct
5 Correct 37 ms 85448 KB Output is correct
6 Correct 37 ms 85444 KB Output is correct
7 Correct 39 ms 85356 KB Output is correct
8 Correct 40 ms 85404 KB Output is correct
9 Correct 38 ms 85336 KB Output is correct
10 Correct 39 ms 85380 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 37 ms 85364 KB Output is correct
3 Correct 38 ms 85328 KB Output is correct
4 Correct 37 ms 85444 KB Output is correct
5 Correct 37 ms 85448 KB Output is correct
6 Correct 37 ms 85444 KB Output is correct
7 Correct 39 ms 85356 KB Output is correct
8 Correct 40 ms 85404 KB Output is correct
9 Correct 38 ms 85336 KB Output is correct
10 Correct 39 ms 85380 KB Output is correct
11 Correct 183 ms 92784 KB Output is correct
12 Correct 46 ms 89396 KB Output is correct
13 Correct 152 ms 89656 KB Output is correct
14 Correct 324 ms 98044 KB Output is correct
15 Correct 156 ms 89936 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 85452 KB Output is correct
2 Correct 37 ms 85364 KB Output is correct
3 Correct 38 ms 85328 KB Output is correct
4 Correct 37 ms 85444 KB Output is correct
5 Correct 37 ms 85448 KB Output is correct
6 Correct 37 ms 85444 KB Output is correct
7 Correct 39 ms 85356 KB Output is correct
8 Correct 40 ms 85404 KB Output is correct
9 Correct 38 ms 85336 KB Output is correct
10 Correct 39 ms 85380 KB Output is correct
11 Correct 183 ms 92784 KB Output is correct
12 Correct 46 ms 89396 KB Output is correct
13 Correct 152 ms 89656 KB Output is correct
14 Correct 324 ms 98044 KB Output is correct
15 Correct 156 ms 89936 KB Output is correct
16 Correct 693 ms 93784 KB Output is correct
17 Correct 934 ms 124492 KB Output is correct
18 Correct 359 ms 96312 KB Output is correct
19 Correct 482 ms 93992 KB Output is correct
20 Correct 683 ms 107100 KB Output is correct