oj.uz

Submission #93254

# Submission time Handle Problem Language Result Execution time Memory
93254 2019-01-07T11:07:07 Z KLPP Robots (APIO13_robots) C++14
0 / 100
 4 ms 512 KB 
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,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];
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);
	int prevdir=dir;
	if(grid[a][b]=='A'){
		dir+=3;
		dir%=4;
	}
	if(grid[a][b]=='C'){
		dir++;
		dir%=4;
	}
	pii ans;
	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;
}
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]);
			}
		}
	}
	priority_queue<pair<int,pii> >pq;
	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()){
		int d=pq.top().first;
		pii pos=pq.top().second;
		pq.pop();
		int x=pos.first;
		int y=pos.second;
		if(d>DP[x][y][a][b])continue;
		for(int dir=0;dir<4;dir++){
			pii 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;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Runtime error 4 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -