답안 #122417

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122417 2019-06-28T07:24:05 Z jakob_nogler 로봇 (APIO13_robots) C++14
30 / 100
1500 ms 74684 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
     
    struct item{
        int val;
        si lo, hi, r, c;
        bool operator < (const item &o) const{
            return val > o.val;
        }
        // item(){}
        // item(int val, si lo, si hi, si r, si c) : val(val), lo(lo), hi(hi), pos.fi(r), pos.se(c){}
    };
     
    priority_queue<item> 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();
            si 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({dp[dict[r][r]][pos.fi][pos.se], 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()){
            int val = q3.top().val;
            si lo = q3.top().lo;
            si hi = q3.top().hi;
            pii pos = {q3.top().r, q3.top().c};
            q3.pop();

            if(lo == 0 && hi == n - 1){
                cout << val << endl;
                return 0;
            }
     
            if(val > dp[dict[lo][hi]][pos.fi][pos.se]) continue;
     
            for(si 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];
                    q3.push({dp[dict[lo][i]][pos.fi][pos.se], lo, i, pos.fi, pos.se});
                
                }
            
            for(si 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];
                    q3.push({dp[dict[i][hi]][pos.fi][pos.se], i, hi, pos.fi, pos.se});
                }
     
            for(si 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;
                    q3.push({dp[dict[lo][hi]][nn.fi][nn.se], 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 2 ms 640 KB Output is correct
2 Correct 2 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 3 ms 1408 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 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 3 ms 1408 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 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 3 ms 1408 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 408 ms 37716 KB Output is correct
12 Correct 32 ms 22392 KB Output is correct
13 Correct 37 ms 24720 KB Output is correct
14 Execution timed out 1570 ms 74684 KB Time limit exceeded
15 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 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 3 ms 1408 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 3 ms 768 KB Output is correct
8 Correct 2 ms 896 KB Output is correct
9 Correct 2 ms 768 KB Output is correct
10 Correct 3 ms 1280 KB Output is correct
11 Correct 408 ms 37716 KB Output is correct
12 Correct 32 ms 22392 KB Output is correct
13 Correct 37 ms 24720 KB Output is correct
14 Execution timed out 1570 ms 74684 KB Time limit exceeded
15 Halted 0 ms 0 KB -