Cod sursa(job #389977)

Utilizator ionutz32Ilie Ionut ionutz32 Data 2 februarie 2010 17:31:11
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <stdio.h>
struct elem
{
	int x,y;
};
int n,m,i,x1,y1,x2,y2,a[505][505],j,c,b,s[505][505],v[2][2000010],mod,ln,col,dir,y,z;
bool ok;
elem mat[8][5]={{1,1,0,1,1,0,-1,1,1,-1},
				{1,0,1,-1,1,1,0,-1,0,1},
				{1,-1,0,-1,1,0,-1,-1,1,1},
				{0,1,-1,1,1,1,-1,0,1,0},
				{0,-1,-1,-1,1,-1,-1,0,1,0},
				{-1,1,-1,0,0,1,-1,-1,1,1},
				{-1,0,-1,-1,-1,1,0,-1,0,1},
				{-1,-1,-1,0,0,-1,-1,1,1,-1}};
int f(int x,bool k)
{
	switch(x)
	{
		case 0:if (k) return 1;else return 3;break;
		case 1:if (k) return 2;else return 0;break;
		case 2:if (k) return 4;else return 1;break;
		case 3:if (k) return 0;else return 5;break;
		case 4:if (k) return 7;else return 2;break;
		case 5:if (k) return 3;else return 6;break;
		case 6:if (k) return 5;else return 7;break;
		case 7:if (k) return 6;else return 4;break;
	}
}
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 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
	{
		b=(x1<<9)+y1;
		for (i=1;i<=n;++i)
			for (j=1;j<=m;++j)
				scanf("%d",&a[i][j]);
		s[x1][y1]=255;
		for (i=0;i<8;++i)
			v[0][++v[0][0]]=b+(i<<18);
		i=0;
		while (v[0][0]+v[1][0])
		{
			mod=i & 1;
			c=1;
			while (c<=v[mod][0])
			{
				dir=v[mod][c]>>18;
				ln=(v[mod][c]>>9) & 511;
				col=v[mod][c] & 511;
				y=ln+mat[dir][0].x;
				z=col+mat[dir][0].y;
				if (y>=1 && y<=n && z>=1 && z<=m && a[y][z]==0 && (s[y][z] & (1<<dir))==0)
				{
					s[y][z]|=1<<dir;
					v[mod][++v[mod][0]]=(dir<<18)+(y<<9)+z;
					if (y==x2 && z==y2)
						ok=true;
				}
				++c;
			}
			c=1;
			while (c<=v[mod][0])
			{
				ln=(v[mod][c]>>9) & 511;
				col=v[mod][c] & 511;
				dir=f(v[mod][c]>>18,false);
				if (!(s[ln][col] & (1<<dir)))
				{
					s[ln][col]|=1<<dir;
					v[1-mod][++v[1-mod][0]]=(dir<<18)+(ln<<9)+col;
				}
				ln=(v[mod][c]>>9) & 511;
				col=v[mod][c] & 511;
				dir=f(v[mod][c]>>18,true);
				if (!(s[ln][col] & (1<<dir)))
				{
					s[ln][col]|=1<<dir;
					v[1-mod][++v[1-mod][0]]=(dir<<18)+(ln<<9)+col;
				}
				++c;
			}
			v[mod][0]=0;
			if (ok)
				break;
			++i;
		}
		if (ok)
			printf("%d",i);
		else
			printf("%d",-1);
	}
	return 0;
}