Submission #4222

#	Time	Username	Problem	Language	Result	Execution time	Memory
4222		cki86201	Robots (APIO13_robots)	C++98	30 / 100	72 ms	163840 KiB

robots

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

//using hasing, O(W*H*N^3);

const int MV = 502*502;
const int ME = 502*502*4*2;	//~=2,000,000;
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];		//using in function make_edge;
bool A[510][510],C[510][510];
bool check[MV];					//using in function Merge;
int Q[MV][2];					//0:depth, 1:tr of point;
short b_check[MV];				//using in function BFS;	assigned by 1~9;
int Dp[9][9][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 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]){
					//printf("%d %d -> %d %d\n",tx,ty,i,j);
					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[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[i][i][j][k])Dp[i][i][j][k] = INF;
			}
		}
	}
}

void Merge(int a,int b,int c)
{
	//assigning Dp[a][c] with Dp[a][b] & Dp[b+1][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[a][b][i][j]==INF || Dp[b+1][c][i][j]==INF)continue;
			int tmp = tr(i,j);
			int tmp2 = Dp[a][b][i][j]+Dp[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[a][c][tmp.first][tmp.second]=min(Dp[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[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[x][y][i][j]=INF;
	}
}

int main()
{
//	freopen("input.txt","r",stdin);
	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++){
			//assigning Dp[j][j+i];
			init(j,j+i);
			for(k=0;k<i;k++){
				//Dp[j][j+i] = Dp[j][j+k]+Dp[j+k+1][j+i];
				Merge(j,j+k,j+i);
			}
		}
	}
	output();
	return 0;
}

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