제출 #408712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408712		Nodir_Bobiev	로봇 (APIO13_robots)	C++17	60 / 100	1567 ms	71796 KiB

robots

/* In the name of Allah */
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

const int inf = 1000000;
int n, w, h;
string grid[510];
int hsh[10][10], dp[50][510][510];
bool vis[4][510][510];
pair < int, int > nxt[4][510][510];
pair < int, int > dirs[4] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} };

bool ok( int x, int y ){
    return( 0 <= x && x < h && 0 <= y && y < w && grid[x][y] != 'x');
}

/*
nxt[d][x][y] = {-1, -1} -> nxt[d][x][y] is not calculated yet;
nxt[d][x][y] = {-2, -2} -> nxt[d][x][y] is not defined. There are a infinite loop;
nxt[d][x][y] is not in {{-2, -2} {-1, -1}} -> nxt[d][x][y] is calculated.
*/

pair < int, int > rec(int d, int x, int y){
    if( nxt[d][x][y] != make_pair(-1, -1) )return nxt[d][x][y];
    if( vis[d][x][y] ) return nxt[d][x][y] = {-2, -2};
    vis[d][x][y] = 1;
    int dd = d;
    if( grid[x][y] == 'A' )if( --dd < 0 ) dd += 4;
    if( grid[x][y] == 'C' )if( ++dd > 3 ) dd -= 4;

    int xx = x + dirs[dd].x, yy = y + dirs[dd].y;
    if( ok(xx, yy) ) return nxt[d][x][y] = rec( dd, xx, yy );
    return nxt[d][x][y] = {x,y};
}

void bfs( int id, priority_queue < vector < int > > q){
    while( !q.empty() ){
        auto fr = q.top(); q.pop();
        int cost = -fr[0], x = fr[1], y = fr[2];
        if( cost != dp[id][x][y] ) continue;
        for( int d = 0; d < 4; d ++ ){
            auto to = nxt[d][x][y];
            if( to != make_pair(-2, -2) && dp[id][x][y] + 1 < dp[id][to.x][to.y] ){
                dp[id][to.x][to.y] = dp[id][x][y] + 1;
                q.push({-dp[id][to.x][to.y], to.x, to.y});
            }
        }
    }
}

int main(){
    cin >> n >> w >> h;
    for( int i = 0; i < h; i ++ )
        cin >> grid[i];

    int cnt = 0;
    for( int i = 0; i < n; i ++ ){
        for( int j = i+1; j <= n; j ++ ){
            hsh[i][j] = cnt++;
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int d = 0; d < 4; d ++ ){
                nxt[d][i][j] = {-1, -1};
            }
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int d = 0; d < 4; d ++ ){
                rec(d, i, j);
            }
        }
    }
    for( int i = 0; i < h; i ++ ){
        for( int j = 0; j < w; j ++ ){
            for( int id = 0; id < cnt; id ++ ){
                dp[id][i][j] = inf;
            }
        }
    }
    for( int id = 0; id < n; id ++ ){
        for( int i = 0; i < h; i ++ ){
            for( int j= 0; j < w; j ++ ){
                if( grid[i][j] == id + 49 ){
                    dp[hsh[id][id+1]][i][j] = 0;
                    priority_queue < vector < int > > pq;
                    pq.push({0, i, j} );
                    bfs(hsh[id][id+1], pq);
                }
            }
        }
    }
    for( int len = 2; len <= n ; len ++ ){
        for( int i = 0; i <= n - len; i ++ ){
            int j = i + len;
            priority_queue < vector < int > > pq;
            for( int x = 0; x < h; x ++ ){
                for( int y = 0; y < w; y ++ ){
                    for( int k = i+1; k < j; k ++ ){
                        if( dp[hsh[i][j]][x][y] > dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y] ){
                            dp[hsh[i][j]][x][y] = dp[hsh[i][k]][x][y] + dp[hsh[k][j]][x][y];
                        }
                    }
                    if( dp[hsh[i][j]][x][y] != inf ) pq.push({-dp[hsh[i][j]][x][y], x, y});
                }
            }
            bfs(hsh[i][j], pq);
        }
    }/*
    for( int d = 0; d < 4; d ++ ){
        cout << "----> " << d << endl;
        for( int i = 0; i < h; i ++ ){
            for( int j = 0; j < w; j ++ ){
                cout << nxt[d][i][j].x << ' ' << nxt[d][i][j].y << "    " ;
            }cout << endl;
        }
    }
    for( int i = 0; i < n; i ++ ){
        for( int j = i+1; j <= n; j ++ ){
            cout << "----> " << i << ' ' << j << endl;
            for( int x = 0; x < h; x ++ ){
                for( int y = 0; y < w; y ++ ){
                    cout << dp[hsh[i][j]][x][y] << ' ';
                }cout << endl;
            }
        }
    }*/
    int res = inf;
    for( int x = 0; x < h; x ++ ){
        for( int y = 0; y < w; y ++ ){
            res = min( res, dp[hsh[0][n]][x][y] );
        }
    }
    if( res == inf ) cout << -1;
    else cout << res;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

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