Submission #162096

#	Time	Username	Problem	Language	Result	Execution time	Memory
162096		HungAnhGoldIBO2020	Robots (APIO13_robots)	C++14	100 / 100	511 ms	125032 KiB

robots

#include<bits/stdc++.h>
using namespace std;
const int N=501;
const int TOTAL=N*N;
const int M=10;
const int inf=1e9+7;
const int LIM=TOTAL*10;
int n,m,dis[M][M][TOTAL],go[5][TOTAL],dx[]={0,-1,0,1},dy[]={-1,0,1,0},nm;
char dime[N][N];
bool valid(int x,int y){
	if(x>=1&&x<=n){
		if(y>=1&&y<=m){
			if(dime[x][y]!='x'){
				return true;
			}
		}
	}
	return false;
}
int idx(int x,int y){
	return (x-1)*m+y;
}
bool cac=true;
int dfs(int dir,int x,int y){
	if(!valid(x,y)){
		return idx(x-dx[dir],y-dy[dir]);
	}
	if(go[dir][idx(x,y)]!=0){
		return go[dir][idx(x,y)];
	}
	go[dir][idx(x,y)]=-1;
	if(dime[x][y]=='C'){
		go[dir][idx(x,y)]=dfs((dir+1)%4,x+dx[(dir+1)%4],y+dy[(dir+1)%4]);
	}
	else{
		if(dime[x][y]=='A'){
			go[dir][idx(x,y)]=dfs((dir+3)%4,x+dx[(dir+3)%4],y+dy[(dir+3)%4]);
		}
		else{
			go[dir][idx(x,y)]=dfs(dir,x+dx[dir],y+dy[dir]);
		}
	}
	return go[dir][idx(x,y)];
}
void bfs(int val,int pos){
	queue<int> q;
	q.push(pos);
	while(q.size()){
		pos=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			if(go[i][pos]!=-1){
				if(dis[val][val][go[i][pos]]>dis[val][val][pos]+1){
					dis[val][val][go[i][pos]]=dis[val][val][pos]+1;
					q.push(go[i][pos]);
				}
			}
		}
	}
}
vector<int> lis[LIM];
void dijkstra(int l,int r){
	int i,j,k,cnt=0;
	for(i=1;i<=nm;i++){
		if(dis[l][r][i]<LIM){
			lis[dis[l][r][i]].push_back(i);
			cnt++;
		}
	}
	for(i=0;i<LIM&&cnt;i++){
		while(lis[i].size()){
			j=lis[i].back();
			lis[i].pop_back();
			cnt--;
			if(dis[l][r][j]!=i||i==LIM-1){
				continue;
			}
			for(k=0;k<4;k++){
				if(go[k][j]!=-1){
					if(dis[l][r][go[k][j]]>dis[l][r][j]+1){
						dis[l][r][go[k][j]]=dis[l][r][j]+1;
						lis[i+1].push_back(go[k][j]);
						cnt++;
					}
				}
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int i,j,k,l,num,z;
	cin>>num>>m>>n;
	nm=n*m;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			cin>>dime[i][j];
		}
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(dime[i][j]=='x'){
				continue;
			}
			for(k=0;k<4;k++){
				if(!go[k][idx(i,j)]){
					dfs(k,i,j);
				}
			}
		}
	}
	//cout<<go[1][47]<<endl;
	for(i=1;i<=n;i++){
		for(j=1;j<=m;j++){
			if(dime[i][j]>='1'&&dime[i][j]<='9'){
				for(k=1;k<=nm;k++){
					dis[(int)(dime[i][j]-'1')][(int)(dime[i][j]-'1')][k]=inf;
				}
				dis[(int)(dime[i][j]-'1')][(int)(dime[i][j]-'1')][idx(i,j)]=0;
				bfs((int)(dime[i][j]-'1'),idx(i,j));
			}
		}
	}
	for(l=1;l<num;l++){
		for(i=0;i+l<num;i++){
			j=i+l;
			for(z=1;z<=nm;z++){
				dis[i][j][z]=inf;
			}
			for(k=i;k<j;k++){		//(i,k) and (k+1,j)
				for(z=1;z<=nm;z++){
					dis[i][j][z]=min(dis[i][j][z],dis[i][k][z]+dis[k+1][j][z]);
				}
			}
			dijkstra(i,j);
		}
	}
	int ans=inf;
	for(i=1;i<=nm;i++){
		ans=min(ans,dis[0][num-1][i]);
	}
	if(ans==inf){
		cout<<-1;
	}
	else{
		cout<<ans;
	}
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/

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