oj.uz

답안 #630877

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630877 2022-08-17T09:45:21 Z MohamedFaresNebili 로봇 (APIO13_robots) C++14
0 / 100
 45 ms 63140 KB 
#include <bits/stdc++.h>

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};

            int N, W, H, D[10][10][505][505];
            vector<array<int, 2>> Q[2250005];
            array<int, 2> G[505][505][5];
            char grid[505][505];

            array<int, 2> dfs(int i, int j, int k) {
                if(G[i][j][k][0] != -1)
                    return G[i][j][k];
                int nxt = k;
                if(grid[i][j] == 'C') nxt = (nxt + 1) % 4;
                if(grid[i][j] == 'A') nxt = (nxt + 3) % 4;
                int x = i + nx[nxt], y = j + ny[nxt];
                if(x < 0 || y < 0 || x >= H || y >= W || grid[x][y] == 'X')
                    return G[i][j][k] = {i, j};
                return G[i][j][k] = dfs(x, y, nxt);
            }
            void update(int i, int j, int x, int y, int d) {
                if(D[i][j][x][y] > d && d < 2250005) {
                    D[i][j][x][y] = d; Q[d].push_back({x, y});
                }
            }
            void solve(int i, int j) {
                for(int l = 0; l < 2250005; l++) {
                    for(auto u : Q[l]) {
                        if(D[i][j][u[0]][u[1]] != l)
                            continue;
                        for(int k = 0; k < 4; k++) {
                            array<int, 2> arr = G[u[0]][u[1]][k];
                            update(i, j, arr[0], arr[1], l + 1);
                        }
                    }
                    Q[l].clear();
                }
            }

            int32_t main() {
                ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
                cin >> N >> W >> H;
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++)
                        cin >> grid[l][i];
                memset(G, -1, sizeof G);
                for(int l = 0; l < W; l++)
                    for(int i = 0; i < W; i++) {
                        for(int j = 0; j < 4; j++)
                            dfs(l, i, j);
                    }
                for(int l = 0; l < N; l++)
                    for(int i = 0; i < N; i++)
                        for(int x = 0; x < H; x++)
                            for(int y = 0; y < W; y++)
                                D[l][i][x][y] = 1e9 + 7;
                for(int l = 0; l < N; l++) {
                    for(int i = l; ~i; i--) {
                        if(i < l) {
                            for(int x = 0; x < H; x++)
                                for(int y = 0; y < W; y++)
                                    for(int j = i; j < l; j++)
                                        update(i, l, x, y, D[i][j][x][y] + D[j + 1][l][x][y]);
                        }
                        else {
                            for(int x = 0; x < H; x++)
                                for(int y = 0; y < W; y++) {
                                    int C = grid[x][y] - '0' - 1;
                                    if(C == l) update(l, l, x, y, 0);
                                }
                        }
                        solve(i, l);
                    }
                }
                int res = -1;
                for(int l = 0; l < H; l++)
                    for(int i = 0; i < W; i++) {
                        if(D[0][N - 1][l][i] < res || res == -1)
                            res = D[0][N - 1][l][i];
                    }
                cout << res << "\n";
                return 0;
            }

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 63052 KB Output is correct
2 Incorrect 45 ms 63140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 63052 KB Output is correct
2 Incorrect 45 ms 63140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 63052 KB Output is correct
2 Incorrect 45 ms 63140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 63052 KB Output is correct
2 Incorrect 45 ms 63140 KB Output isn't correct
3 Halted 0 ms 0 KB -