Submission #490739

#	Time	Username	Problem	Language	Result	Execution time	Memory
490739		phamhoanghiep	Robots (APIO13_robots)	C++14	100 / 100	609 ms	156704 KiB

robots

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf=1e9;
int dp[10][10][505][505];
char c[505][505];
vector<ii> dist[505*505+5];
bool vis[505][505];
vector<ii> AdjList[505][505];
int n,h,w;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
bool ok(int x, int y) {
    return x>=1&&x<=h&&y>=1&&y<=w&&c[x][y]!='x';
}
ii run(int x, int y, int id) {
    //cout<<"go "<<x<<" "<<y<<" "<<id<<endl;
    while(true) {
        //cout<<x<<" "<<y<<endl;
        if(c[x][y]=='C') id=(id+1)%4;
        if(c[x][y]=='A') id=(id+3)%4;
        int nx=x+dx[id];
        int ny=y+dy[id];
        if(!ok(nx,ny)) return ii(x,y);
        x=nx; y=ny;
    }
}
void bfs(int l, int r) {
    //cout<<"bfs "<<l<<" "<<r<<endl;
    for(int i=1 ; i<=h ; i++) {
        for(int j=1 ; j<=w ; j++) {
            vis[i][j]=0;
        }
    }
    for(int i=0 ; i<=505*505 ; i++) {
        dist[i].clear();
    }
    int mn=inf;
    int mx=0;
    for(int i=1 ; i<=h ; i++) {
        for(int j=1 ; j<=w ; j++) {
            if(dp[l][r][i][j]!=-1) {
                //cout<<"dp "<<l<<" "<<r<<" "<<i<<" "<<j<<" = "<<dp[l][r][i][j]<<endl;
                dist[dp[l][r][i][j]].push_back(ii(i,j));
                mn=min(dp[l][r][i][j],mn);
                mx=max(dp[l][r][i][j],mx);
            }
        }
    }
    for(int i=0 ; i<=505*505 ; i++) {
        for(ii tmp: dist[i]) {
            int x=tmp.first;
            int y=tmp.second;
            if(vis[x][y]) continue;
            else vis[x][y]=1;
            for(ii tmp1: AdjList[x][y]) {
                int nx=tmp1.first; int ny=tmp1.second;
                //cout<<"nx ny = "<<nx<<" "<<ny<<endl;
                if(dp[l][r][nx][ny]>dp[l][r][x][y]+1||dp[l][r][nx][ny]==-1) {
                    dp[l][r][nx][ny]=dp[l][r][x][y]+1;
                    dist[dp[l][r][nx][ny]].push_back(ii(nx,ny));
                }
            }
        }
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n;
    cin>>w>>h;
    memset(dp,-1,sizeof(dp));
    for(int i=1 ; i<=h ; i++) {
        cin>>c[i]+1;
        for(int j=1 ; j<=w ; j++) {
            if(c[i][j]>='0'&&c[i][j]<='9') {
                int x=c[i][j]-'0';
                dp[x][x][i][j]=0;
            }
        }
    }
    for(int i=1 ; i<=h ; i++) {
        for(int j=1 ; j<=w ; j++) {
            for(int id=0 ; id<4 ; id++) {
                AdjList[i][j].push_back(run(i,j,id));
                //cout<<"go "<<i<<" "<<j<<" "<<(5-id)%4<<" = "<<run(i,j,id).first<<" "<<run(i,j,id).second<<endl;
            }
        }
    }
    for(int d=0 ; d<n ; d++) {
        for(int l=1 ; l+d<=n ; l++) {
            int r=l+d;
            for(int mid=l ; mid<r ; mid++) {
                for(int x=1 ; x<=h ; x++) {
                    for(int y=1 ; y<=w ; y++) {
                        if((dp[l][r][x][y]==-1||dp[l][r][x][y]>dp[l][mid][x][y]+dp[mid+1][r][x][y])&&(dp[l][mid][x][y]!=-1&&dp[mid+1][r][x][y]!=-1))
                            dp[l][r][x][y]=dp[l][mid][x][y]+dp[mid+1][r][x][y];
                    }
                }
            }
            bfs(l,r);
        }
    }
    int ans=inf;
    for(int i=1 ; i<=h ; i++) {
        for(int j=1 ; j<=w ; j++) {
            if(dp[1][n][i][j]!=-1) ans=min(ans,dp[1][n][i][j]);
        }
    }
    if(ans==inf) cout<<-1;
    else cout<<ans;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:74:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |         cin>>c[i]+1;
      |              ~~~~^~

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