| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 93258 | KLPP | Robots (APIO13_robots) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<queue>
using namespace std;
typedef pair<short int,short int> pii;
int n,m,r;
char grid[500][500];
pii moves[500][500][4];
int DP[500][500][9][9];
bool computed[9][9];
priority_queue<pair<int,pii> >pq;
pii ans;
int prevdir;
pii Move(int a, int b,int dir){
//cout<<a<<" "<<b<<" "<<dir<<endl;
if(a<0 || n<=a || b<0 || m<=b)return pii(-1,-1);
if(moves[a][b][dir].first!=-1)return moves[a][b][dir];
if(grid[a][b]=='x')return pii(-1,-1);
prevdir=dir;
if(grid[a][b]=='A'){
dir+=3;
dir%=4;
}
if(grid[a][b]=='C'){
dir++;
dir%=4;
}
if(dir==0){
ans=Move(a,b+1,dir);
}if(dir==1){
ans=Move(a+1,b,dir);
}if(dir==2){
ans=Move(a,b-1,dir);
}if(dir==3){
ans=Move(a-1,b,dir);
}
if(ans.first==-1){
ans=pii(a,b);
}
moves[a][b][prevdir]=ans;
return ans;
}
int d;
pii pos,next;
int x,y;
void compute(int a, int b){
if(computed[a][b])return;
for(int med=a;med<b;med++){
compute(a,med);
compute(med+1,b);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
DP[i][j][a][b]=min(DP[i][j][a][b],DP[i][j][a][med]+DP[i][j][med+1][b]);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
pq.push(pair<int,pii>(DP[i][j][a][b],pii(i,j)));
}
}
while(!pq.empty()){
d=pq.top().first;
pos=pq.top().second;
pq.pop();
x=pos.first;
y=pos.second;
if(d>DP[x][y][a][b])continue;
for(int dir=0;dir<4;dir++){
next=Move(x,y,dir);
if(DP[next.first][next.second][a][b]>d+1){
DP[next.first][next.second][a][b]=d+1;
pq.push(pair<int,pii>(d+1,next));
}
}
}
computed[a][b]=true;
}
int main(){
cin>>r>>m>>n;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<4;k++)moves[i][j][k]=pii(-1,-1);
cin>>grid[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
for(int k=0;k<r;k++){
for(int l=k;l<r;l++){
DP[i][j][k][l]=1000000000;
}
}
}
}
for(int k=0;k<r;k++){
for(int l=k;l<r;l++){computed[k][l]=false;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(grid[i][j]>='0' && grid[i][j]<='9'){
DP[i][j][grid[i][j]-'1'][grid[i][j]-'1']=0;
}
}
}
compute(0,r-1);
int ans=1000000000;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ans=min(ans,DP[i][j][0][r-1]);
//cout<<DP[i][j][0][r-1]<<" ";
}//cout<<endl;
}cout<<ans<<endl;
//cout<<Move(0,0,2).first<<" "<<Move(0,0,2).second<<endl;
return 0;
}