답안 #122073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122073 2019-06-27T13:54:59 Z jakob_nogler 로봇 (APIO13_robots) C++14
0 / 100
138 ms 163840 KB
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
typedef tuple<int, int, int, int> tiiii;
typedef tuple<int, int, int, int, int> tiiiii;

const int N = 505;
const int dir = 4;
const int R = 9;
const int inf = 10e8;

pii nxt[N][N][dir];
int cost[R][N][N], dp[R][R][20][20];
bool vis0[N][N][dir];
char grid[N][N];
int n, w, h;

int dr[dir] = {1, 0, - 1, 0};
int dc[dir] = {0, 1, 0, - 1}; //down, right, up, left

queue<tiiii> q3[N * N];

int main(){
    cin >> n >> w >> h;
    w += 2; h += 2;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++){
            grid[i][j] = 'x';
            for(int k = 0; k < dir; k++)
                nxt[i][j][k] = {- 1, - 1};
            for(int k = 0; k < n; k++)
                cost[k][i][j] = - 1;
            for(int k = 0; k < n; k++)
                for(int l = 0; l < n; l++)
                    dp[k][l][i][j] = inf;
        }


    queue<tiii> q0, q1;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++){
            cin >> grid[i][j];
            if(grid[i][j] >= '1' && grid[i][j] <= '9'){
                cost[grid[i][j] - '1'][i][j] = 0;
                q1.push({grid[i][j] - '1', i, j});
            }
        }

    /*for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++)
            cout << grid[i][j] << " ";
        cout << endl;
    }*/

    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            for(int k = 0; k < dir; k++)
                if(grid[i][j] != 'x' && grid[i + dr[k]][j + dc[k]] == 'x'){
                    q0.push({i, j, k});
                    nxt[i][j][k] = {i, j};
                }

    while(!q0.empty()){
        tiii curr = q0.front();
        q0.pop();
        int d = get<2>(curr), id, mov;
        pii pos = {get<0>(curr), get<1>(curr)};

        if(grid[pos.fi][pos.se] == 'A') mov = (d + 1) % 4, id = (d + 3) % 4;
        else if(grid[pos.fi][pos.se] == 'C') mov = (d + 3) % 4, id = (d + 1) % 4;
        else mov = (d + 2) % 4, id = d;
        if(grid[pos.fi + dr[mov]][pos.se + dc[mov]] == 'x') continue;
        nxt[pos.fi + dr[mov]][pos.se + dc[mov]][id] = nxt[pos.fi][pos.se][d];
        q0.push({pos.fi + dr[mov], pos.se + dc[mov], id});
    }

    set<tiiiii> s;
    while(!q1.empty()){
        tiii curr = q1.front();
        q1.pop();
        int r = get<0>(curr);
        pii pos = {get<1>(curr), get<2>(curr)};

        dp[r][r][pos.fi][pos.se] = cost[r][pos.fi][pos.se];
        q3[cost[r][pos.fi][pos.se]].push({r, r, pos.fi, pos.se});


        for(int i = 0; i < dir; i++){
            pii nn = nxt[pos.fi][pos.se][i];
            if(cost[r][nn.fi][nn.se] == - 1){
                cost[r][nn.fi][nn.se] = cost[r][pos.fi][pos.se] + 1;
                q1.push({r, nn.fi, nn.se});
            }
        }
    }

    for(int v = 0; v < 20; v++){
        while(!q3[v].empty()){
            tiiii curr = q3[v].front();
            q3[v].pop();

            int lo = get<0>(curr), hi = get<1>(curr);
            pii pos = {get<2>(curr), get<3>(curr)};

            if(dp[lo][hi][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[lo][i][pos.fi][pos.se] > dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[lo][i][pos.fi][pos.se] = dp[hi + 1][i][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[lo][i][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[i][hi][pos.fi][pos.se] > dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se]){
                    dp[i][hi][pos.fi][pos.se] = dp[i][lo - 1][pos.fi][pos.se] + dp[lo][hi][pos.fi][pos.se];
                    q3[dp[i][hi][pos.fi][pos.se]].push({i, hi, pos.fi, pos.se});
                }

            for(int i = 0; i < dir; i++){
                pii nn = nxt[pos.fi][pos.se][i];
                if(dp[lo][hi][nn.fi][nn.se] > dp[lo][hi][pos.fi][pos.se] + 1){
                    dp[lo][hi][nn.fi][nn.se] = dp[lo][hi][pos.fi][pos.se] + 1;
                    q3[dp[lo][hi][nn.fi][nn.se]].push({lo, hi, nn.fi, nn.se});
                }
            }
        }
    }

    int ans = inf;
    for(int i = 1; i < h - 1; i++)
        for(int j = 1; j < w - 1; j++)
            ans = min(ans, dp[0][n - 1][i][j]);

    if(ans == inf) cout << - 1 << endl;
    else cout << ans << endl;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 138 ms 163840 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -