답안 #122140

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122140 2019-06-27T16:46:21 Z jakob_nogler 로봇 (APIO13_robots) C++14
30 / 100
244 ms 38560 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;
    
pii nxt[N][N][dir];
int cost[R][N][N], dp[sum][N][N], dict[R][R];
bool vis[sum][N][N];
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;
    
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];
        vis[dict[r][r]][pos.fi][pos.se] = true;
        q3.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});
            }
        }
    }

    while(!q3.empty()){
        tiiii curr = q3.front();
        q3.pop();

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

        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]){
                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(!vis[dict[lo][i]][pos.fi][pos.se]){
                     q3.push({lo, i, pos.fi, pos.se});
                     vis[dict[lo][i]][pos.fi][pos.se] = true;
                }
            }
        
        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]){
                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(!vis[dict[i][hi]][pos.fi][pos.se]){
                    q3.push({i, hi, pos.fi, pos.se});
                    vis[dict[i][hi]][pos.fi][pos.se] = true;
                }
            }

        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){
                dp[dict[lo][hi]][nn.fi][nn.se] = dp[dict[lo][hi]][pos.fi][pos.se] + 1;
                if(!vis[dict[lo][hi]][nn.fi][nn.se]){
                    q3.push({lo, hi, nn.fi, nn.se});
                    vis[dict[lo][hi]][nn.fi][nn.se] = true;
                }
            }
        }
    }
    
    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 2 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1296 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1296 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1296 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
11 Correct 136 ms 33044 KB Output is correct
12 Correct 93 ms 22148 KB Output is correct
13 Correct 35 ms 24952 KB Output is correct
14 Incorrect 244 ms 38560 KB Output isn't correct
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 2 ms 1408 KB Output is correct
5 Correct 2 ms 1296 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 2 ms 768 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 3 ms 1408 KB Output is correct
11 Correct 136 ms 33044 KB Output is correct
12 Correct 93 ms 22148 KB Output is correct
13 Correct 35 ms 24952 KB Output is correct
14 Incorrect 244 ms 38560 KB Output isn't correct
15 Halted 0 ms 0 KB -