Submission #784578

#	Time	Username	Problem	Language	Result	Execution time	Memory
784578		resolve100	Robots (APIO13_robots)	C++14	30 / 100	1577 ms	90720 KiB

robots

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

using namespace std;

const int N = 500;
int dp[N][N][9][9];

char grid[N][N];
int rows, cols, n;

bool is_valid(int x, int y){
    return (x < cols && x >= 0 && y < rows && y >= 0 && grid[y][x] != 'x');
}

//void dfs_all(int x, int y, int start, int end, int dist){
//    for (int dir = 0; dir < 4; dir++){
//        int dx=0, dy=0;
//        if (dir == 0) dx = -1;
//        if (dir == 1) dy = 1;
//        if (dir == 2) dx = 1;
//        if (dir == 3) dy = -1;
//        if (is_valid(x+dx, y+dy)){
//            bfs(x, y, start, end, dir, dist+1);
//        }
//    }
//}

void bfs(int x, int y, int start, int end, int dist, int dir){
    if (!is_valid(x, y)) return;
    if (grid[y][x] == 'A'){
        dir+=1;
        dir=(dir%4);
    }
    else if(grid[y][x] == 'C'){
        dir+=3;
        dir=(dir%4);
    }

    int dx=0, dy=0;
    if (dir == 0) dx = -1;
    if (dir == 1) dy = 1;
    if (dir == 2) dx = 1;
    if (dir == 3) dy = -1;

    if (is_valid(x+dx, y+dy)){
        bfs(x+dx, y+dy, start, end, dist, dir);
    }
    else{
        if (dp[y][x][start][end] == -1 || dp[y][x][start][end] > dist) {
            dp[y][x][start][end] = dist;
            bfs(x-1, y, start, end, dp[y][x][start][end]+1, 0);
            bfs(x, y+1, start, end, dp[y][x][start][end]+1, 1);
            bfs(x+1, y, start, end, dp[y][x][start][end]+1, 2);
            bfs(x, y-1, start, end, dp[y][x][start][end]+1, 3);

            int r1 = start-1;
            for (int l1 = 0; l1 < start; l1++){
                if (dp[y][x][l1][r1] != -1 && (dp[y][x][l1][end] == -1 || dp[y][x][l1][end] > dp[y][x][l1][r1]+dist)){
                    dp[y][x][l1][end] = dist+dp[y][x][l1][r1];
                    bfs(x-1, y, l1, end, dp[y][x][l1][end]+1, 0);
                    bfs(x, y+1, l1, end, dp[y][x][l1][end]+1, 1);
                    bfs(x+1, y, l1, end, dp[y][x][l1][end]+1, 2);
                    bfs(x, y-1, l1, end, dp[y][x][l1][end]+1, 3);

                }
            }
            int l2 = end+1;
            for (int r2 = end+1; r2 < n; r2++){
                if (dp[y][x][l2][r2] != -1 && (dp[y][x][end][r2] == -1 || dp[y][x][end][r2] > dp[y][x][l2][r2]+dist)){
                    dp[y][x][start][r2] = dist+dp[y][x][l2][r2];
                    bfs(x-1, y, start, r2, dp[y][x][start][r2]+1, 0);
                    bfs(x, y+1, start, r2, dp[y][x][start][r2]+1, 1);
                    bfs(x+1, y, start, r2, dp[y][x][start][r2]+1, 2);
                    bfs(x, y-1, start, r2, dp[y][x][start][r2]+1, 3);
                }
            }

            for (int l1 = 0; l1 < start; l1++){
                for (int r2 = end+1; r2 < n; r2++){
                    if (dp[y][x][l1][start] != -1 && dp[y][x][end][r2] != -1 && (dp[y][x][l1][r2] == -1 || dp[y][x][l1][r2] > dp[y][x][l1][start]+dp[y][x][end][r2]+dist)){
                        dp[y][x][l1][r2] = dp[y][x][l1][start]+dp[y][x][end][r2]+dist;
                        bfs(x-1, y, l1, r2, dp[y][x][l1][r2]+1, 0);
                        bfs(x, y+1, l1, r2, dp[y][x][l1][r2]+1, 1);
                        bfs(x+1, y, l1, r2, dp[y][x][l1][r2]+1, 2);
                        bfs(x, y-1, l1, r2, dp[y][x][l1][r2]+1, 3);
                    }
                }
            }
        }
    }
}

void solve(){
    memset(dp, -1, sizeof(dp));

    cin >> n >> cols >> rows;

    for (int y = 0; y < rows; y++){
        for (int x = 0; x < cols; x++){
            cin >> grid[y][x];
            if ( (grid[y][x]-'0') >= 1 && (grid[y][x]-'0') <= 9){
                int dig = (grid[y][x]-'0')-1;
                dp[y][x][dig][dig] = 0;
            }
        }
    }

    for (int y = 0; y < rows; y++){
        for (int x = 0; x < cols; x++){
            if (grid[y][x]-'0' >= 1 && grid[y][x]-'0' <= 9){
                int dig = (grid[y][x]-'0')-1;
                bfs(x-1, y, dig, dig, 1, 0);
                bfs(x, y+1, dig, dig, 1, 1);
                bfs(x+1, y, dig, dig, 1, 2);
                bfs(x, y-1, dig, dig, 1, 3);
            }
        }
    }

    bool ok = false;
    int ans = INFINITY;
    for (int y = 0; y < rows; y++){
        for (int x = 0; x < cols; x++){
            if (dp[y][x][0][n-1] != -1){
                ans = min(ans, dp[y][x][0][n-1]);
                ok = true;
            }
        }
    }

    if (ok){
        cout << ans << endl;
    }
    else{
        cout << -1 << endl;
    }
}

int main() {
    fast;
    int t = 1;
    while (t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'void solve()':
robots.cpp:125:15: warning: overflow in conversion from 'float' to 'int' changes value from '+Inff' to '2147483647' [-Woverflow]
  125 |     int ans = INFINITY;
      |               ^~~~~~~~

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