oj.uz

답안 #580891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
580891 2022-06-22T05:26:58 Z 반딧불(#8360) 로봇 (APIO13_robots) C++17
30 / 100
 84 ms 32508 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;
    }
}

struct dat{
    int x, y, d;
    dat(){}
    dat(int x, int y, int d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};
bool visited[502][502];

void calculateDP(int l, int r){
    memset(visited, 0, sizeof(visited));
    vector<dat> vec;
    queue<dat> que;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(DP[l][r][i][j] >= 1e9) continue;
            vec.push_back(dat(i, j, DP[l][r][i][j]));
        }
    }
    sort(vec.begin(), vec.end());
    int pnt = 0;

    while(!que.empty() || pnt < (int)vec.size()){
        if(que.empty()){
            que.push(vec[pnt++]);
        }
        dat tmp;
        if(pnt < (int)vec.size() && vec[pnt].d <= que.front().d) tmp = vec[pnt++];
        else tmp = que.front(), que.pop();
        int x = tmp.x, y = tmp.y, d = tmp.d;
//        printf("%d %d %d\n", x, y, d);
        if(d>=1e9 || visited[x][y]) continue;
        DP[l][r][x][y] = d;
        visited[x][y] = 1;
        for(int c=0; c<4; c++){
            if(endpointX[x][y][c] == -1) continue;
            if(visited[endpointX[x][y][c]][endpointY[x][y][c]]) continue;
            que.push(dat(endpointX[x][y][c], endpointY[x][y][c], d+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
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 0 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Incorrect 84 ms 32508 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 0 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Incorrect 84 ms 32508 KB Output isn't correct
12 Halted 0 ms 0 KB -