oj.uz

Submission #580884

# Submission time Handle Problem Language Result Execution time Memory
580884 2022-06-22T05:14:10 Z 반딧불(#8360) Robots (APIO13_robots) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int xx[]={0, -1, 0, 1}, yy[]={1, 0, -1, 0};

int n, m, k;
char board[502][502];
int sx[10], sy[10];

void input();
void operate();
void output();

int main(){
    input();
    operate();
    output();
}

void input(){
    scanf("%d %d %d", &k, &m, &n);
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) board[i][j] = 'x';
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        scanf(" %c", &board[i][j]);
        if(isdigit(board[i][j])){
            int tmp = board[i][j] - '0';
            sx[tmp] = i, sy[tmp] = j;
            board[i][j] = '.';
        }
    }
}

int endpointX[502][502][4];
int endpointY[502][502][4];

void calculateEndpoints(){
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int d=0; d<4; d++) endpointX[i][j][d] = -1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(board[i][j]=='x') continue;
            for(int d=0; d<4; d++){
                if(board[i+xx[d]][j+yy[d]]!='x') continue;
                int x=i, y=j, td=d;
                while(board[x][y]!='x'){
                    if(board[x][y]=='A') td=(td+3)%4;
                    if(board[x][y]=='C') td=(td+1)%4;
                    endpointX[x][y][td] = i;
                    endpointY[x][y][td] = j;
                    x-=xx[td], y-=yy[td];
                }
            }
        }
    }
}

int DP[10][10][502][502];

void init(){
    for(int l=1; l<=k; l++) for(int r=l; r<=k; r++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        DP[l][r][i][j] = 1e9;
    }
    for(int i=1; i<=k; i++){
        DP[i][i][sx[i]][sy[i]] = 0;
    }
}

void calculateDP(int l, int r){
    bool change = 1;
    int cnt = 0;
    while(change && ++cnt <= 10){
        change = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(board[i][j]=='#') continue;
                for(int d=0; d<4; d++){
                    if(endpointX[i][j][d] == -1) continue;
                    if(DP[l][r][endpointX[i][j][d]][endpointY[i][j][d]] > DP[l][r][i][j]+1){
                        change = 1;
                        DP[l][r][endpointX[i][j][d]][endpointY[i][j][d]] = DP[l][r][i][j]+1;
                    }
                }
            }
        }
    }
}

void operate(){
    calculateEndpoints();
    init();
    for(int d=0; d<k; d++){
        for(int i=1; i+d<=k; i++){
            int j = i+d;
            for(int mid=i; mid<j; mid++){
                for(int x=1; x<=n; x++){
                    for(int y=1; y<=m; y++){
                        DP[i][j][x][y] = min(DP[i][j][x][y], DP[i][mid][x][y] + DP[mid+1][j][x][y]);
                    }
                }
            }
            calculateDP(i, j);
        }
    }

    #ifdef TEST
    for(int i=1; i<=k; i++) for(int j=i; j<=k; j++){
        printf("Matrix %d %d:\n", i, j);
        for(int x=1; x<=n; x++){
            for(int y=1; y<=m; y++){
                printf("%3d ", DP[i][j][x][y]>100?100:DP[i][j][x][y]);
            }
            puts("");
        }
    }
    #endif
}

void output(){
    int ans = INT_MAX;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans = min(ans, DP[1][k][i][j]);
    if(ans >= 1e9) printf("-1");
    else printf("%d", ans);
}

Compilation message

robots.cpp: In function 'void input()':
robots.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d %d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %c", &board[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Incorrect 1 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -