Cod sursa(job #389890)

Utilizator ionutz32Ilie Ionut ionutz32 Data 2 februarie 2010 13:50:28
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <stdio.h>
#define inf 5000000
struct elem
{
	int x,y;
};
int n,m,i,x1,y1,x2,y2,a[505][505],j,c,b,s[505][505][8],sol,v[3][2000010],t,d,mod,mod2,ln,col,dir,y,z,q,cost;
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 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);
	sol=inf;
	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]);
				for (c=0;c<8;++c)
					s[i][j][c]=inf;
			}
		for (i=0;i<8;++i)
		{
			v[0][++v[0][0]]=b+(i<<18);
			s[x1][y1][i]=0;
		}
		i=0;
		while (v[0][0]+v[1][0]+v[2][0])
		{
			c=1;
			mod=i%3;
			while (c<=v[mod][0])
			{
				dir=v[mod][c]>>18;
				ln=(v[mod][c]>>9) & 511;
				col=v[mod][c] & 511;
				if (s[ln][col][dir]==i)
					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);
						cost=(j+1)>>1;
						if (y>=1 && y<=n && z>=1 && z<=m && a[y][z]==0 && i+cost<s[y][z][q])
						{
							s[y][z][q]=i+cost;
							v[s[y][z][q]%3][++v[s[y][z][q]%3][0]]=(q<<18)+(y<<9)+z;
							if (y==x2 && z==y2)
							{
								ok=true;
								if ((t & (1<<q))==0)
								{
									++d;
									t|=1<<q;
								}
							}
						}
					}
				++c;
			}
			if (d==8)
				break;
			v[mod][0]=0;
			++i;
		}
		if (ok)
		{
			sol=inf;
			for (i=0;i<8;++i)
				if (s[x2][y2][i]<sol)
					sol=s[x2][y2][i];
			printf("%d",sol);
		}
		else
			printf("%d",-1);
	}
	return 0;
}