| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93259 |
2019-01-07T11:17:48 Z |
KLPP |
Robots (APIO13_robots) |
C++14 |
|
4 ms |
508 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
