Submission #4232

#	Time	Username	Problem	Language	Result	Execution time	Memory
4232		cki86201	Robots (APIO13_robots)	C++98	100 / 100	888 ms	156920 KiB

robots

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;

const int MV = 502*502;
const int ME = 502*502*4*2;
const int INF = 100000000;
int n,w,h;
int xx[4]={-1,0,1,0}, yy[4]={0,1,0,-1};
char ch[510][510];
bool wall[510][510];
bool m_check[4][510][510];
bool A[510][510],C[510][510];
bool check[MV];
int Q[MV][2];
short b_check[MV];
int Dp[46][502][502];

typedef pair<int,int> P;
P inp[10];
int st[MV],en[ME];
int next[ME];
int c_edge;
vector <int> Hash[2500020];

inline int T(int x,int y){return (y+1)*y/2+x;}
inline int tr(int x,int y){return 500*(x-1)+y;}
P itr(int x){return P((x-1)/500+1,(x-1)%500+1);}
void addedge(int s,int d)
{
	++c_edge;
	next[c_edge]=st[s];
	st[s]=c_edge;
	en[c_edge]=d;
}

void make_edge()
{
	int i,j,k;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			for(k=0;k<4;k++){
				if(wall[i+xx[k^2]][j+yy[k^2]])continue;
				int ink = k;
				int tx = i, ty = j;
				if(A[i][j])ink=(ink+1)%4;
				else if(C[i][j])ink=(ink?ink-1:3);
				while(!m_check[ink][tx][ty] && wall[tx][ty]){
					addedge(tr(tx,ty),tr(i,j));
					m_check[ink][tx][ty]=1;
					tx+=xx[ink];
					ty+=yy[ink];
					if(A[tx][ty])ink=(ink+1)%4;
					else if(C[tx][ty])ink=(ink?ink-1:3);
				}
			}
		}
	}
}

void BFS(int x)
{
	int fr=1,re=0;
	int vx = tr(inp[x].first,inp[x].second);
	Q[0][0]=vx,Q[0][1]=0;
	b_check[vx]=x+1;
	while(fr!=re){
		int i;
		int tx = Q[re][0];
		for(i=st[tx];i;i=next[i]){
			if(b_check[en[i]] == x+1)continue;
			b_check[en[i]]=x+1;
			Q[fr][0]=en[i];
			Q[fr][1]=Q[re][1]+1;
			fr++;
		}
		P tmp = itr(Q[re][0]);
		Dp[T(x,x)][tmp.first][tmp.second]=Q[re][1];
		re++;
	}
}

void Init()
{
	int i,j,k;
	for(i=0;i<n;i++){
		for(j=1;j<=h;j++){
			for(k=1;k<=w;k++){
				if(inp[i]==P(j,k))continue;
				if(!Dp[T(i,i)][j][k])Dp[T(i,i)][j][k] = INF;
			}
		}
	}
}

void Merge(int a,int b,int c)
{
	memset(check,0,sizeof(check));
	int max_num=0;
	int i,j;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			if(Dp[T(a,b)][i][j]==INF || Dp[T(b+1,c)][i][j]==INF)continue;
			int tmp = tr(i,j);
			int tmp2 = Dp[T(a,b)][i][j]+Dp[T(b+1,c)][i][j];
			Hash[tmp2].push_back(tmp);
			max_num = max(max_num,tmp2);
		}
	}
	for(i=1;i<=max_num;i++){
		if(Hash[i].empty())continue;
		for(j=0;j<Hash[i].size();j++){
			if(check[Hash[i][j]])continue;
			check[Hash[i][j]]=1;
			P tmp = itr(Hash[i][j]);
			Dp[T(a,c)][tmp.first][tmp.second]=min(Dp[T(a,c)][tmp.first][tmp.second],i);
			for(int k=st[Hash[i][j]];k;k=next[k]){
				if(check[en[k]])continue;
				Hash[i+1].push_back(en[k]);
				max_num=max(max_num,i+1);
			}
		}
		Hash[i].clear();
	}
}

void output()
{
	int i,j,ans=INF;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++){
			ans=min(ans,Dp[T(0,n-1)][i][j]);
		}
	}
	printf("%d",ans==INF?-1:ans);
}

void init(int x,int y)
{
	int i,j;
	for(i=1;i<=h;i++){
		for(j=1;j<=w;j++)Dp[T(x,y)][i][j]=INF;
	}
}

int main()
{
	scanf("%d%d%d",&n,&w,&h);
	int i,j,k;
	for(i=1;i<=h;i++){
		scanf("%s",ch[i]+1);
		for(j=1;j<=w;j++){
			if(ch[i][j]!='x')wall[i][j]=1;
			if(ch[i][j]<='9'&&ch[i][j]>='1')inp[ch[i][j]-'1']=P(i,j);
			if(ch[i][j]=='A')A[i][j]=1;
			else if(ch[i][j]=='C')C[i][j]=1;
		}
	}
	make_edge();
	for(i=0;i<n;i++)BFS(i);
	Init();
	for(i=1;i<n;i++){
		for(j=0;j<n-i;j++){
			init(j,j+i);
			for(k=0;k<i;k++){
				Merge(j,j+k,j+i);
			}
		}
	}
	output();
	return 0;
}

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