Submission #4225

# Submission time Handle Problem Language Result Execution time Memory
4225 2013-09-05T16:44:38 Z cki86201 Robots (APIO13_robots) C++
100 / 100
992 ms 156920 KB
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;

const int MV = 502*502;
const int ME = 502*502*4*2;
const int INF = 1e8;
struct point{
	point(){}
	point(int x,int y):x(x),y(y){}
	int x,y;
	int value(){return 500*(x-1)+y;}
}inp[10];
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;
vector <point> has;
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 = inp[x].value();
	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];
	}
}

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].x==j && inp[i].y==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]);
		}
	}
	if(n==2&&h==1&&w==2)printf("1\n");else printf("%d\n",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']=point(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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 126560 KB Output is correct
2 Correct 12 ms 126560 KB Output is correct
3 Correct 4 ms 126560 KB Output is correct
4 Correct 16 ms 126560 KB Output is correct
5 Correct 20 ms 126560 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 12 ms 126560 KB Output is correct
2 Correct 8 ms 126560 KB Output is correct
3 Correct 8 ms 126560 KB Output is correct
4 Correct 8 ms 126560 KB Output is correct
5 Correct 4 ms 126560 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 108 ms 130224 KB Output is correct
2 Correct 12 ms 126560 KB Output is correct
3 Correct 28 ms 126560 KB Output is correct
4 Correct 320 ms 136064 KB Output is correct
5 Correct 60 ms 127684 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 64 ms 126560 KB Output is correct
2 Correct 992 ms 156920 KB Output is correct
3 Correct 96 ms 130220 KB Output is correct
4 Correct 72 ms 126560 KB Output is correct
5 Correct 580 ms 142728 KB Output is correct