Submission #1168546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168546		byunjaewoo	Robots (APIO13_robots)	C++20	60 / 100	1596 ms	67360 KiB

robots

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

const int N=10, X=510, INF=1e9;
int n, h, w, ans=INF, x[N], y[N], a[X][X], nxt[X][X], dp[N][N][X][X];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};
vector<pair<int, int>> adj[X][X];
priority_queue<array<int, 3>> pq;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>w>>h;
    for(int i=1; i<=h; i++) {
        string s; cin>>s;
        for(int j=1; j<=w; j++) {
            if('1'<=s[j-1] && s[j-1]<='9') x[s[j-1]-'0']=i, y[s[j-1]-'0']=j;
            else if(s[j-1]=='A') a[i][j]=1;
            else if(s[j-1]=='C') a[i][j]=2;
            else if(s[j-1]=='x') a[i][j]=-1;
        }
    }
    for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) {
        for(int d=0; d<4; d++) {
            int ii=i, jj=j, dd=d;
            while(true) {
                if(ii+dx[dd]<1 || ii+dx[dd]>h || jj+dy[dd]<1 || jj+dy[dd]>w || a[ii+dx[dd]][jj+dy[dd]]<0) break;
                ii+=dx[dd], jj+=dy[dd];
                if(a[ii][jj]==1) dd=(dd+3)%4;
                if(a[ii][jj]==2) dd=(dd+1)%4;
            }
            if(i!=ii || j!=jj) adj[i][j].push_back({ii, jj});
        }
    }
    for(int l=1; l<=n; l++) for(int r=l; r<=n; r++) for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) dp[l][r][i][j]=INF;
    for(int i=1; i<=n; i++) dp[i][i][x[i]][y[i]]=0;
    for(int d=1; d<=n; d++) {
        for(int l=1; l<=n-d+1; l++) {
            int r=l+d-1;
            for(int k=l; k<r; k++) for(int i=1; i<=h; i++) for(int j=1; j<=w; j++)
                dp[l][r][i][j]=min(dp[l][r][i][j], dp[l][k][i][j]+dp[k+1][r][i][j]);
            for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) pq.push({-dp[l][r][i][j], i, j});
            while(!pq.empty()) {
                auto [d, i, j]=pq.top(); pq.pop();
                d=-d;
                if(dp[l][r][i][j]<d) continue;
                for(auto [ii, jj]:adj[i][j]) if(dp[l][r][ii][jj]>d+1) {
                    dp[l][r][ii][jj]=d+1;
                    pq.push({-d-1, ii, jj});
                }
            }
        }
    }
    for(int i=1; i<=h; i++) for(int j=1; j<=w; j++) ans=min(ans, dp[1][n][i][j]);
    if(ans>=INF/10) ans=-1;
    cout<<ans;
    return 0;
}

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