oj.uz

Submission #490722

# Submission time Handle Problem Language Result Execution time Memory
490722 2021-11-29T02:22:01 Z phamhoanghiep Robots (APIO13_robots) C++14
30 / 100
 136 ms 119824 KB 
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int dp[10][10][501][501];
char c[501][501];
vector<ii> dist[500*500+1];
bool vis[501][501];
vector<ii> AdjList[501][501];
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';
}
int id(int x, int y) {
    return (x-1)*w+y;
}
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<=n*n ; i++) {
        dist[i].clear();
    }
    int mn=w*h+1;
    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);
            }
        }
    }
    queue<ii> q;
    while(!dist[mn].empty()) {
        q.push(dist[mn].back());
        dist[mn].pop_back();
    }
    while(!q.empty()) {
        ii tmp=q.front();
        q.pop();
        int x=tmp.first;
        int y=tmp.second;
        //cout<<"dp "<<l<<" "<<r<<" "<<x<<" "<<y<<" = "<<dp[l][r][x][y]<<endl;
        if(vis[x][y]) continue;
        vis[x][y]=1;
        while(!dist[dp[l][r][x][y]].empty()) {
            q.push(dist[dp[l][r][x][y]].back());
            dist[dp[l][r][x][y]].pop_back();
        }
        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) {
                q.push(ii(nx,ny));
                dp[l][r][nx][ny]=dp[l][r][x][y]+1;
            }
        }
    }
}
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));
            }
        }
    }
    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=w*h+1;
    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==w*h+1) cout<<-1;
    else cout<<ans;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 110244 KB Output is correct
2 Correct 52 ms 110212 KB Output is correct
3 Correct 44 ms 110236 KB Output is correct
4 Correct 46 ms 110280 KB Output is correct
5 Correct 49 ms 110256 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 110244 KB Output is correct
2 Correct 52 ms 110212 KB Output is correct
3 Correct 44 ms 110236 KB Output is correct
4 Correct 46 ms 110280 KB Output is correct
5 Correct 49 ms 110256 KB Output is correct
6 Correct 43 ms 110184 KB Output is correct
7 Correct 45 ms 110228 KB Output is correct
8 Correct 44 ms 110276 KB Output is correct
9 Correct 42 ms 110184 KB Output is correct
10 Correct 44 ms 110288 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 110244 KB Output is correct
2 Correct 52 ms 110212 KB Output is correct
3 Correct 44 ms 110236 KB Output is correct
4 Correct 46 ms 110280 KB Output is correct
5 Correct 49 ms 110256 KB Output is correct
6 Correct 43 ms 110184 KB Output is correct
7 Correct 45 ms 110228 KB Output is correct
8 Correct 44 ms 110276 KB Output is correct
9 Correct 42 ms 110184 KB Output is correct
10 Correct 44 ms 110288 KB Output is correct
11 Incorrect 136 ms 119824 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 110244 KB Output is correct
2 Correct 52 ms 110212 KB Output is correct
3 Correct 44 ms 110236 KB Output is correct
4 Correct 46 ms 110280 KB Output is correct
5 Correct 49 ms 110256 KB Output is correct
6 Correct 43 ms 110184 KB Output is correct
7 Correct 45 ms 110228 KB Output is correct
8 Correct 44 ms 110276 KB Output is correct
9 Correct 42 ms 110184 KB Output is correct
10 Correct 44 ms 110288 KB Output is correct
11 Incorrect 136 ms 119824 KB Output isn't correct
12 Halted 0 ms 0 KB -