Cod sursa(job #389491)

Utilizator ionutz32Ilie Ionut ionutz32 Data 1 februarie 2010 19:12:53
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <stdio.h>
#define inf 5000000
struct elem
{
	int x,y,cost;
};
int n,m,i,x1,y1,x2,y2,a[505][505],j,c,b,d,s[505][505],t[2000010],sol,v[3][2000010];
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;
			v[(i+mat[dir][j].cost)%3][++v[(i+mat[dir][j].cost)%3][0]]=((y-1)*m+z)*8+q;
			++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)
		{
			v[0][++v[0][0]]=b*8+i;
			t[b*8+i]=0;
		}
		d=8;
		s[x1][y1]=255;
		i=0;
		while (d)
		{
			c=1;
			while (c<=v[i%3][0])
			{
				if (t[v[i%3][c]]==i)
					expand(v[i%3][c]);
				--d;
				++c;
			}
			v[i%3][0]=0;
			++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;
}