Submission #909164

#TimeUsernameProblemLanguageResultExecution timeMemory
909164Sir_Ahmed_ImranRobots (APIO13_robots)C++17
30 / 100
342 ms129152 KiB
///~~~LOTA~~~/// #include <bits/stdc++.h> using namespace std; #define nl '\n' #define ff first #define ss second #define ll long long #define append push_back #define pii pair<long long,long long> #define all(x) (x).begin(),(x).end() #define int long long #define N 502 #define M 10 int n,m,o; char c[N][N]; vector<pii> a[N][N]; int dist[N][N][M][M]; void mark(int x,int y,int p,int q,int r,int s){ if(!x || x>n || !y || y>m) return; if(c[x][y]=='x'){ p=x+r; q=y+s; } else if(p!=x || q!=y) a[x][y].append({p,q}); if(c[x][y]=='C'){ swap(r,s); r=-r; } if(c[x][y]=='A'){ swap(r,s); s=-s; } mark(x+r,y+s,p,q,r,s); } void dijkstra(int l,int r){ int d,p,q; priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> Q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(dist[i][j][l][r]<1e17) Q.push({dist[i][j][l][r],{i,j}}); while(!Q.empty()){ d=Q.top().ff; p=Q.top().ss.ff; q=Q.top().ss.ss; Q.pop(); if(d==dist[p][q][l][r]){ for(auto& i:a[p][q]){ if(d+1<dist[i.ff][i.ss][l][r]){ dist[i.ff][i.ss][l][r]=d+1; Q.push({d+1,i}); } } } } } void solve(){ int s; cin>>o>>m>>n; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>c[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int l=1;l<=o;l++) for(int r=l;r<=o;r++) dist[i][j][l][r]=1e17; for(int i=1;i<=n;i++){ mark(i,1,i,1,0,1); mark(i,m,i,m,0,-1); } for(int i=1;i<=m;i++){ mark(1,i,1,i,1,0); mark(n,i,n,i,-1,0); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ s=c[i][j]-'0'; if(s>0 && s<10){ dist[i][j][s][s]=0; dijkstra(s,s); } } } for(int j=1;j<o;j++){ for(int i=1;i+j<=o;i++){ for(int p=1;p<=n;p++) for(int q=1;q<=m;q++) for(int d=i;d<i+j;d++) dist[p][q][i][i+j]=min(dist[p][q][i][i+j] ,dist[p][q][i][d]+dist[p][q][d+1][i+j]); dijkstra(i,i+j); } } s=1e17; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s=min(s,dist[i][j][1][o]); if(s==1e17) s=-1; cout<<s; } signed main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...