Submission #1292529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292529		kiteyu	Robots (APIO13_robots)	C++20	100 / 100	540 ms	143748 KiB

robots

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ll = long long;
const int INF = 500*500+5;
const int N = 500;
const int dx[] = {0,-1,0,1};
const int dy[] = {-1,0,1,0};

int dp[N+5][N+5][10][10];
pair<int,int> nxt[N+5][N+5][4];
int vis[N+5][N+5][4];
int n,h,w;
char a[N+5][N+5];

void init(){
    cin >> n >> w >> h;
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            cin >> a[i][j];
//    cout << a[2][1] << '\n';
}

bool chk_in(int x,int y){
    return (1 <= x && x <= h && 1 <= y && y <= w);
}

pair<int,int> go(int x,int y,int d){
    while(true) {
        if(a[x][y] == 'A') d = (d + 3) % 4;
        if(a[x][y] == 'C') d = (d + 1) % 4;
        int nx = x + dx[d];
        int ny = y + dy[d];
        if(!chk_in(nx, ny) || a[nx][ny] == 'x') break;
        x = nx;
        y = ny;
    }
    return make_pair(x, y);
}

void build(){
//    cout << a[2][1] << '\n';
//    go(1,2,3);
    for(int i = 1 ; i <= h ; ++i){
        for(int j = 1 ; j <= w ; ++j){
            if(a[i][j] == 'x') {
                for(int l = 0 ; l < 4 ; ++l)
                nxt[i][j][l] = {-1,-1};
                continue;
            }
            for(int l = 0 ; l < 4 ; ++l)
                nxt[i][j][l] = go(i,j,l);
        }
    }
}

vector<pair<int,int>> q[N*N+5];
int head = 0,tail = 0;
int head1 = 0, tail1 = 0;

void sol(){
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            for(int l = 0 ; l < 9 ; ++l)
                for(int r = 0 ; r < 9 ; ++r)
                dp[i][j][l][r] = INF;
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            if('1' <= a[i][j] && a[i][j] <= '9'){
                dp[i][j][a[i][j]-'1'][a[i][j]-'1']=0;
            }
    build();
//    for(int i = 1 ; i <= h ; ++i){
//        for(int j = 1 ; j <= w ; ++j){
//            for(int l = 0 ; l < 4 ; ++l)
//            cout << i << ' ' << j << ' ' << l << ' ' << nxt[i][j][l].fi << ',' << nxt[i][j][l].se << '\n';
//        }
//    }

    for(int len = 1 ; len <= n ; ++len){
        for(int l = 0 ; l < n ; ++l){
            int r = l + len - 1;
            if(r >= n) break;
            for(int i = 1 ; i <= h ; ++i)
                for(int j = 1 ; j <= w ; ++j)
                    if(a[i][j] != 'x'){
                        for(int k = l ; k < r ; ++k)
                            dp[i][j][l][r] = min(dp[i][j][l][r],dp[i][j][l][k]+dp[i][j][k+1][r]);
//                        if(l == 2 && r == 2) cout << i << ' ' << j << ' ' << dp[i][j][l][r] << "!\n";
                        if(dp[i][j][l][r]<INF) q[dp[i][j][l][r]].emplace_back(i,j);
                    }


            for(int i = 0 ; i < N * N ; ++i){
                while(!q[i].empty()){
                    pair<int,int> t = q[i].back();
//                    if(l == 2 && r == 2) cout << t.fi << ' ' << t.se << ' ' << i << '\n';
                    q[i].pop_back();
                    if(i > dp[t.fi][t.se][l][r]) continue;
                    for(int j = 0 ; j < 4 ; ++j){
                        pair<int,int> _t = nxt[t.fi][t.se][j];
                        if(_t.fi != -1 && i + 1 < dp[_t.fi][_t.se][l][r]){
                            dp[_t.fi][_t.se][l][r] = i + 1;
                            if(i + 1 < N * N)
                            q[i+1].emplace_back(_t.fi,_t.se);
                        }
                    }
                }
            }
//            if(l == 2 && r == 2){
//                for(int i = 1 ; i <= h ; ++i){
//                    for(int j = 1 ; j <= w ; ++j)
//                        cout << dp[i][j][l][r] << ' ';
//                    cout << '\n';
//                }
//                cout << '\n';
//            }

        }
    }
    int ans = INF;
    for(int i = 1 ; i <= h ; ++i)
        for(int j = 1 ; j <= w ; ++j)
            ans = min(ans,dp[i][j][0][n-1]);
    if(ans >= INF) cout << -1;
    else
    cout << ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    init();
    sol();
    return 0;
}

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