Submission #422329

#	Time	Username	Problem	Language	Result	Execution time	Memory
422329		SirCovidThe19th	Robots (APIO13_robots)	C++14	100 / 100	1101 ms	125928 KiB

robots

#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)

const int mx = 500;

int n, w, h, ans = 505*505, dp[mx][mx][9][9], di[4] = {-1, 0, 1, 0}, dj[4] = {0, 1, 0, -1}; 
char grid[mx][mx]; pair<int, int> pos[4][mx][mx]; vector<pair<int, int>> trav[mx*mx];

pair<int, int> nextPos(int i, int j, int d){
    int old = d; d = (d-(grid[i][j] == 'A')+(grid[i][j] == 'C')+4)%4;
    int r = i+di[d], c = j+dj[d]; pos[old][i][j] = {-2, -2}; pair<int, int> ret;
    if (!(r < h and r >= 0 and c < w and c >= 0 and grid[r][c] != 'x')) ret = {i, j};
    else if (pos[d][r][c] != make_pair(-1, -1)) ret = pos[d][r][c];
    else ret = nextPos(r, c, d);
    return pos[old][i][j] = ret;
}

int main(){
    cin >> n >> w >> h; memset(dp, 0x3f, sizeof(dp));
    FOR(i, 0, h) FOR(j, 0, w) { cin >> grid[i][j]; if (isdigit(grid[i][j])) dp[i][j][grid[i][j]-'1'][grid[i][j]-'1'] = 0; }
    FOR(i, 0, h) FOR(j, 0, w) FOR(d, 0, 4) pos[d][i][j] = {-1, -1};
    FOR(i, 0, h) FOR(j, 0, w) FOR(d, 0, 4) if (grid[i][j] != 'x') nextPos(i, j, d);
    FOR(l, 0, n){
        FOR(x, 0, n-l){
            int y = x+l; 
            FOR(i, 0, h) FOR(j, 0, w) if (grid[i][j] != 'x'){
                FOR(mid, x, y)
                    dp[i][j][x][y] = min(dp[i][j][x][y], dp[i][j][x][mid]+dp[i][j][mid+1][y]);
                if (dp[i][j][x][y] < w*h) trav[dp[i][j][x][y]].push_back({i, j});
            }
            FOR(i, 0, w*h){
                for (pair<int, int> curr : trav[i]){
                    int r = curr.first, c = curr.second;
                    FOR(d, 0, 4){
                        int r1, c1; tie(r1, c1) = pos[d][r][c]; 
                        if (r1 < 0 or c1 < 0) continue;
                        if (dp[r][c][x][y]+1 < dp[r1][c1][x][y]){
                            dp[r1][c1][x][y] = dp[r][c][x][y]+1;
                            trav[dp[r1][c1][x][y]].push_back({r1, c1});
                        }
                    }
                }
                trav[i].clear();
            }
        }
    }
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n-1]);
    cout<<((ans > w*h) ? -1 : ans);
}

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