oj.uz

답안 #408725

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
408725 2021-05-19T14:44:04 Z Nodir_Bobiev 로봇 (APIO13_robots) C++17
30 / 100
 1500 ms 33296 KB 
/* 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, queue < pair < int, int > > q){
    while( !q.empty() ){
        auto fr = q.front(); q.pop();
        int x = fr.x, y = fr.y;
        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({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;
                    queue < pair < int, int > > pq;
                    pq.push({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;
            queue < pair < int, 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({x, y});
                }
            }
            bfs(hsh[i][j], pq);
        }
    }
    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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Execution timed out 1576 ms 33296 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Execution timed out 1576 ms 33296 KB Time limit exceeded
12 Halted 0 ms 0 KB -