Submission #93259

#	Time	Username	Problem	Language	Result	Execution time	Memory
93259		KLPP	Robots (APIO13_robots)	C++14	0 / 100	4 ms	508 KiB

robots

#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;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40