oj.uz

Submission #241282

# Submission time Handle Problem Language Result Execution time Memory
241282 2020-06-23T16:11:22 Z dolphingarlic Robots (APIO13_robots) C++14
0 / 100
 83 ms 158968 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, h, w;
char grid[500][500];
pair<int, int> end_pos[500][500][4];
ll dp[500][500][9][9];

bool inside(int x, int y) {
    return (x >= 0 && y >= 0 && x < h && y < w && grid[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 >> grid[i][j];
        if (grid[i][j] - '0' > 0 && grid[i][j] - '0' < 10) {
            dp[i][j][grid[i][j] - '1'][grid[i][j] - '1'] = 0;
        }
    }

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

        while (true) {
            if (curr_dir == 0) {
                if (inside(curr_pos.first - 1, curr_pos.second))
                    curr_pos.first--;
                else
                    break;
            } else if (curr_dir == 1) {
                if (inside(curr_pos.first, curr_pos.second + 1))
                    curr_pos.second++;
                else
                    break;
            } else if (curr_dir == 2) {
                if (inside(curr_pos.first + 1, curr_pos.second))
                    curr_pos.first++;
                else
                    break;
            } else {
                if (inside(curr_pos.first, curr_pos.second - 1))
                    curr_pos.second--;
                else
                    break;
            }

            if (grid[curr_pos.first][curr_pos.second] == 'A') {
                curr_dir = (curr_dir + 3) % 4;
            } else if (grid[curr_pos.first][curr_pos.second] == 'C') {
                curr_dir = (curr_dir + 1) % 4;
            }
        }

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

    FOR(rng, 0, n) {
        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(div, k, l) FOR(i, 0, h) FOR(j, 0, w) {
                dp[i][j][k][l] = min(dp[i][j][k][l],
                                     dp[i][j][k][div] + dp[i][j][div + 1][l]);
            }
        }

        FOR(k, 0, n - rng) {
            int l = k + rng;
            FOR(i, 0, h) FOR(j, 0, w) {
                FOR(dir, 0, 4) {
                    int nx, ny;
                    tie(nx, ny) = end_pos[i][j][dir];
                    dp[nx][ny][k][l] =
                        min(dp[nx][ny][k][l], dp[i][j][k][l] + 1);
                }
            }
        }
    }

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 158840 KB Output is correct
2 Correct 83 ms 158844 KB Output is correct
3 Correct 83 ms 158840 KB Output is correct
4 Incorrect 83 ms 158968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 158840 KB Output is correct
2 Correct 83 ms 158844 KB Output is correct
3 Correct 83 ms 158840 KB Output is correct
4 Incorrect 83 ms 158968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 158840 KB Output is correct
2 Correct 83 ms 158844 KB Output is correct
3 Correct 83 ms 158840 KB Output is correct
4 Incorrect 83 ms 158968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 158840 KB Output is correct
2 Correct 83 ms 158844 KB Output is correct
3 Correct 83 ms 158840 KB Output is correct
4 Incorrect 83 ms 158968 KB Output isn't correct
5 Halted 0 ms 0 KB -