답안 #122408

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122408 2019-06-28T07:18:15 Z jakob_nogler 로봇 (APIO13_robots) C++14
30 / 100
169 ms 110360 KB
#include <bits/stdc++.h>
#define fi first
#define se second
    
using namespace std;
    
typedef short int si;
typedef pair<si, si> pii;
typedef tuple<si, si, si> tiii;
typedef tuple<si, si, si, si> tiiii;
    
const int N = 355, dir = 4, R = 9, inf = 10e8, sum = R * (R + 1) / 2;
const int lim = sum;

pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
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 < sum; k++)
                dp[k][i][j] = inf;
        }
    
    int idx = 0;
    for(int i = 0; i < R; i++)
        for(int j = i; j < R; j++)
            dict[i][j] = idx++;
    
    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 = 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});
    }
    
    while(!q1.empty()){
        tiii curr = q1.front();
        q1.pop();
        int r = get<0>(curr);
        pii pos = {get<1>(curr), get<2>(curr)};
    
        dp[dict[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 < N * N; 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(lo == 0 && hi == n - 1){
                cout << v << endl;
                return 0;
            }
    
            if(dp[dict[lo][hi]][pos.fi][pos.se] < v) continue;
            for(int i = hi + 1; i < n; i++)
                if(dp[dict[lo][i]][pos.fi][pos.se] > dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    int val = dp[dict[lo][i]][pos.fi][pos.se] = dp[dict[hi + 1][i]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    if(val < lim) q3[dp[dict[lo][i]][pos.fi][pos.se]].push({lo, i, pos.fi, pos.se});
                }
            for(int i = lo - 1; i >= 0; i--)
                if(dp[dict[i][hi]][pos.fi][pos.se] > dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se]){
                    int val = dp[dict[i][hi]][pos.fi][pos.se] = dp[dict[i][lo - 1]][pos.fi][pos.se] + dp[dict[lo][hi]][pos.fi][pos.se];
                    if(val < lim) q3[dp[dict[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[dict[lo][hi]][nn.fi][nn.se] > dp[dict[lo][hi]][pos.fi][pos.se] + 1){
                    int val = dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
                    if(val < lim) q3[dp[dict[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[dict[0][n - 1]][i][j]);
    
    if(ans == inf) cout << - 1 << endl;
    else cout << ans << endl;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 85496 KB Output is correct
2 Correct 82 ms 85496 KB Output is correct
3 Correct 80 ms 85512 KB Output is correct
4 Correct 80 ms 86236 KB Output is correct
5 Correct 80 ms 86264 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 85496 KB Output is correct
2 Correct 82 ms 85496 KB Output is correct
3 Correct 80 ms 85512 KB Output is correct
4 Correct 80 ms 86236 KB Output is correct
5 Correct 80 ms 86264 KB Output is correct
6 Correct 79 ms 85636 KB Output is correct
7 Correct 94 ms 85468 KB Output is correct
8 Correct 96 ms 85624 KB Output is correct
9 Correct 97 ms 85700 KB Output is correct
10 Correct 98 ms 86140 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 85496 KB Output is correct
2 Correct 82 ms 85496 KB Output is correct
3 Correct 80 ms 85512 KB Output is correct
4 Correct 80 ms 86236 KB Output is correct
5 Correct 80 ms 86264 KB Output is correct
6 Correct 79 ms 85636 KB Output is correct
7 Correct 94 ms 85468 KB Output is correct
8 Correct 96 ms 85624 KB Output is correct
9 Correct 97 ms 85700 KB Output is correct
10 Correct 98 ms 86140 KB Output is correct
11 Incorrect 169 ms 110360 KB Output isn't correct
12 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 85496 KB Output is correct
2 Correct 82 ms 85496 KB Output is correct
3 Correct 80 ms 85512 KB Output is correct
4 Correct 80 ms 86236 KB Output is correct
5 Correct 80 ms 86264 KB Output is correct
6 Correct 79 ms 85636 KB Output is correct
7 Correct 94 ms 85468 KB Output is correct
8 Correct 96 ms 85624 KB Output is correct
9 Correct 97 ms 85700 KB Output is correct
10 Correct 98 ms 86140 KB Output is correct
11 Incorrect 169 ms 110360 KB Output isn't correct
12 Halted 0 ms 0 KB -