제출 #122417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122417		jakob_nogler	로봇 (APIO13_robots)	C++14	30 / 100	1570 ms	74684 KiB

robots

    #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;
    }

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40