Cod sursa(job #389480)

Utilizator ionutz32Ilie Ionut ionutz32 Data 1 februarie 2010 18:51:13
Problema Car Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <stdio.h>
#define inf 5000000
struct node
{
	int x;
	node *adr;
};
struct elem
{
	int x,y,cost;
};
node *v[3],*u,*u2,*sf[3];
int n,m,i,x1,y1,x2,y2,a[505][505],j,c,b,d,s[505][505],t[2000010],sol;
elem vector[4]={0,0,0,1,1,1,2,2,2,3,3,3};
bool ok;
elem mat[8][5]={{-1,1,2,0,1,1,1,-1,2,1,0,1,1,1,0},
				{0,-1,2,0,1,2,1,-1,1,1,0,0,1,1,1},
				{-1,-1,2,0,-1,1,1,-1,0,1,0,1,1,1,2},
				{-1,0,2,-1,1,1,0,1,0,1,0,2,1,1,1},
				{-1,-1,1,-1,0,2,0,-1,0,1,-1,1,1,0,2},
				{-1,-1,2,-1,0,1,-1,1,0,0,1,1,1,1,2},
				{-1,-1,1,-1,0,0,-1,1,1,0,-1,2,0,1,2},
				{-1,-1,0,-1,0,1,-1,1,2,0,-1,1,1,-1,2}};
int p(int a,int b)
{
	if (a==-1 && b==-1) return 7;
	if (a==-1 && !b) return 6;
	if (a==-1 && b==1) return 5;
	if (!a && b==-1) return 4;
	if (!a && b==1) return 3;
	if (a==1 && b==-1) return 2;
	if (a==1 && !b) return 1;
	if (a==1 && b==1) return 0;
}
int inm(int ln,int col)
{
	return (ln>=1 && ln<=n && col>=1 && col<=m);
}
void expand(int nod)
{
	int ln,col,dir,y,z,q;
	dir=nod%8;
	nod=nod/8;
	if (nod%m==0)
	{
		ln=nod/m;
		col=m;
	}
	else
	{
		ln=nod/m+1;
		col=nod%m;
	}
	for (j=0;j<5;++j)
	{
		y=ln+mat[dir][j].x;
		z=col+mat[dir][j].y;
		q=p(mat[dir][j].x,mat[dir][j].y);
		if (inm(y,z) && a[y][z]==0 && ((s[y][z] & (1<<q))==0 || i+mat[dir][j].cost<t[((y-1)*m+z)*8+q]))
		{
			s[y][z]|=1<<q;
			u2=new node;
			if (sf[(i+mat[dir][j].cost)%3]==NULL)
			{
				sf[(i+mat[dir][j].cost)%3]=u2;
				v[(i+mat[dir][j].cost)%3]=u2;
			}
			u2->x=((y-1)*m+z)*8+q;
			u2->adr=NULL;
			if (sf[(i+mat[dir][j].cost)%3]!=u2)
				sf[(i+mat[dir][j].cost)%3]->adr=u2;
			sf[(i+mat[dir][j].cost)%3]=u2;
			++d;
			if (y==x2 && z==y2)
				ok=true;
			t[((y-1)*m+z)*8+q]=i+mat[dir][j].cost;
		}
	}
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d %d %d %d %d %d",&n,&m,&x1,&y1,&x2,&y2);
	if (x1==x2 && y1==y2)
		printf("%d",0);
	else
	{
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				for (c=0;c<8;++c)
					t[((i-1)*m+j)*8+c]=-1;
		b=(x1-1)*m+y1;
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				scanf("%d",&a[i][j]);
		for (i=0;i<8;++i)
		{
			u=new node;
			if (sf[0]==NULL)
			{
				sf[0]=u;
				v[0]=u;
			}
			u->x=b*8+i;
			u->adr=NULL;
			if (sf[0]!=u)
				sf[0]->adr=u;
			sf[0]=u;
			t[b*8+i]=0;
		}
		d=8;
		s[x1][y1]=255;
		i=0;
		while (d)
		{
			u=v[i%3];
			while (u!=NULL)
			{
				if (t[u->x]==i)
					expand(u->x);
				--d;
				u=u->adr;
			}
			v[i%3]=NULL;
			sf[i%3]=NULL;
			++i;
		}
		if (ok)
		{
			sol=inf;
			for (i=0;i<8;++i)
				if (t[((x2-1)*m+y2)*8+i]<sol && t[((x2-1)*m+y2)*8+i]>=0)
					sol=t[((x2-1)*m+y2)*8+i];
			printf("%d",sol);
		}
		else
			printf("%d",-1);
	}
	return 0;
}