oj.uz

Submission #490739

# Submission time Handle Problem Language Result Execution time Memory
490739 2021-11-29T03:04:28 Z phamhoanghiep Robots (APIO13_robots) C++14
100 / 100
 609 ms 156704 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 112068 KB Output is correct
2 Correct 55 ms 112076 KB Output is correct
3 Correct 52 ms 112104 KB Output is correct
4 Correct 48 ms 112196 KB Output is correct
5 Correct 51 ms 112040 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 112068 KB Output is correct
2 Correct 55 ms 112076 KB Output is correct
3 Correct 52 ms 112104 KB Output is correct
4 Correct 48 ms 112196 KB Output is correct
5 Correct 51 ms 112040 KB Output is correct
6 Correct 48 ms 112004 KB Output is correct
7 Correct 48 ms 112052 KB Output is correct
8 Correct 62 ms 112048 KB Output is correct
9 Correct 63 ms 111980 KB Output is correct
10 Correct 57 ms 112100 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 112068 KB Output is correct
2 Correct 55 ms 112076 KB Output is correct
3 Correct 52 ms 112104 KB Output is correct
4 Correct 48 ms 112196 KB Output is correct
5 Correct 51 ms 112040 KB Output is correct
6 Correct 48 ms 112004 KB Output is correct
7 Correct 48 ms 112052 KB Output is correct
8 Correct 62 ms 112048 KB Output is correct
9 Correct 63 ms 111980 KB Output is correct
10 Correct 57 ms 112100 KB Output is correct
11 Correct 174 ms 120516 KB Output is correct
12 Correct 63 ms 117032 KB Output is correct
13 Correct 140 ms 116652 KB Output is correct
14 Correct 281 ms 125576 KB Output is correct
15 Correct 149 ms 117700 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 112068 KB Output is correct
2 Correct 55 ms 112076 KB Output is correct
3 Correct 52 ms 112104 KB Output is correct
4 Correct 48 ms 112196 KB Output is correct
5 Correct 51 ms 112040 KB Output is correct
6 Correct 48 ms 112004 KB Output is correct
7 Correct 48 ms 112052 KB Output is correct
8 Correct 62 ms 112048 KB Output is correct
9 Correct 63 ms 111980 KB Output is correct
10 Correct 57 ms 112100 KB Output is correct
11 Correct 174 ms 120516 KB Output is correct
12 Correct 63 ms 117032 KB Output is correct
13 Correct 140 ms 116652 KB Output is correct
14 Correct 281 ms 125576 KB Output is correct
15 Correct 149 ms 117700 KB Output is correct
16 Correct 474 ms 124328 KB Output is correct
17 Correct 609 ms 156704 KB Output is correct
18 Correct 244 ms 128312 KB Output is correct
19 Correct 379 ms 124348 KB Output is correct
20 Correct 360 ms 139184 KB Output is correct