Submission #477904

#	Time	Username	Problem	Language	Result	Execution time	Memory
477904		bin1st090104	Robots (APIO13_robots)	C++11	100 / 100	546 ms	151332 KiB

robots

#include <bits/stdc++.h>

using namespace std;

int const maxK=9;
int const maxN=5e2;
int const inf=0x3f3f3f3f;

int K,N,M;
char c[maxN+3][maxN+3];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
pair<int,int> F[maxN+3][maxN+3][4],F_null={0,0};
int G[maxK+3][maxK+3][maxN+3][maxN+3];

pair<int,int> Cal_F(int i,int j,int d){
	if(F[i][j][d]!=F_null){
		return F[i][j][d];
	}
	pair<int,int>&Res=F[i][j][d];
	int newd=d;
	if(c[i][j]=='A'){
		--newd;
		if(newd<0){
			newd+=4;
		}
	}
	if(c[i][j]=='C'){
		++newd;
		if(newd>=4){
			newd-=4;
		}
	}
	int u=i+dx[newd];
	int v=j+dy[newd];
	if(u<1||N<u||v<1||M<v||c[u][v]=='x'){
		Res={i,j};
	}
	else{
		Res=Cal_F(u,v,newd);
	}
	return Res;
}

struct Data{
	int i,j,x;
	Data(int i=0,int j=0,int x=0):i(i),j(j),x(x){}
};

bool Gmin(int&x,int y){
	return x>y?x=y,true:false;
}

int main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>K>>M>>N;
	for(int i=1;i<=N;++i){
		cin>>c[i]+1;
	}
	for(int i=1;i<=N;++i){
		for(int j=1;j<=M;++j){
			for(int d=0;d<4;++d){
				if(c[i][j]!='x'){
					Cal_F(i,j,d);
				}
			}
		}
	}
	memset(G,0x3f,sizeof G);
	for(int i=1;i<=N;++i){
		for(int j=1;j<=M;++j){
			if(isdigit(c[i][j])){
				G[c[i][j]-'0'][c[i][j]-'0'][i][j]=0;
			}
		}
	}
	vector<Data> Sta,Tmp;
	Sta.reserve(N*M);
	Tmp.reserve(N*M);
	for(int r=1;r<=K;++r){
		for(int l=r;l>=1;--l){
			for(int i=1;i<=N;++i){
				for(int j=1;j<=M;++j){
					for(int k=l;k<r;++k){
						G[l][r][i][j]=min(G[l][r][i][j],G[l][k][i][j]+G[k+1][r][i][j]);
					}
					if(G[l][r][i][j]!=inf){
						Sta.push_back(Data(i,j,G[l][r][i][j]));
					}
				}
			}
			sort(Sta.begin(),Sta.end(),
				[&](Data const&lhs,Data const&rhs){
					return lhs.x>rhs.x;
				});
			while(!Sta.empty()){
				int Val=Sta.back().x;
				while(!Sta.empty()&&Sta.back().x==Val){
					Tmp.push_back(Sta.back());
					Sta.pop_back();
				}
				while(!Tmp.empty()){
					int i=Tmp.back().i;
					int j=Tmp.back().j;
					int x=Tmp.back().x;
					Tmp.pop_back();
					for(int k=0;k<4;++k){
						int u=F[i][j][k].first;
						int v=F[i][j][k].second;
						if(Gmin(G[l][r][u][v],x+1)){
							Sta.push_back(Data(u,v,G[l][r][u][v]));
						}
					}
				}
			}
		}
	}
	int Res=inf;
	for(int i=1;i<=N;++i){
		for(int j=1;j<=M;++j){
			Gmin(Res,G[1][K][i][j]);
		}
	}
	cout<<(Res==inf?-1:Res);
	return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |   cin>>c[i]+1;
      |        ~~~~^~

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