Cod sursa(job #400569)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 21 februarie 2010 17:20:35
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<iostream.h>
#include<fstream.h>

ifstream f("car.in");
ofstream g("car.out");

int x1[10],x2[10],x,y,l1,c1,n,m,xi,xf,yi,yf,dir,w;

int sw[502][502][8],a[502][502];

int l[3][2800000],p[3];

void afisare()
{
	int i,min=1000000;
	for (i=0;i<8;i++)
		if (min>sw[xf][yf][i] && sw[xf][yf][i]>-1)
			min=sw[xf][yf][i];
	g<<min;
}

void add (int k, int C)
{
	int i;
	dir=(k>>18);
	x= (k>>9) & 511;
	y= (k&511);
	if (sw[x][y][dir]<C) return ;
	for (i=0;i<8;i++)
	if (abs(dir-i)<=2 || 8-abs(i-dir)<=2)
	{
		w=abs(dir-i);
		if (w>2) w=8-abs(dir-i);
		l1=x+x1[i];
		c1=y+x2[i];
		if (l1>0 && l1<=n && c1>0 && c1<=m && a[l1][c1]==0 && (sw[l1][c1][i]==-1 || sw[l1][c1][i]>C+w ))
		{
			sw[l1][c1][i]=C+w;
			w=(C+w)%3;
			l[w][++l[w][0]]=(i<<18)+(l1<<9)+c1;
		}
	}
}

void init()
{
	int i;
	for (i=0;i<8;i++)
	{
		l[0][++l[0][0]]=(i<<18)+(xi<<9)+yi;
		sw[xi][yi][i]=0;
	}
}


void compute()
{
	init();
	int C,c,i;
	C=0;
	for (i=0;i<8;i++)
		sw[xi][yi][i]=0;
	while (l[0][0]+l[1][0]+l[2][0]-p[0]-p[1]-p[2]>0)
	{
		c=C%3;
		while (l[c][0]-p[c]>0)
			add(l[c][++p[c]],C);
		C++;
	}
}

void citire()
{
	int i,j,k;
	f>>n>>m;
	f>>xi>>yi>>xf>>yf;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			for (k=0;k<8;k++)
				sw[i][j][k]=-1;
			f>>a[i][j];
		}
	f.close();
	
	x1[0]=-1;x2[0]=0;
	x1[1]=-1;x2[1]=1;
	x1[2]=0; x2[2]=1;
	x1[3]=1;x2[3]=1;
	x1[4]=1;x2[4]=0;
	x1[5]=1;x2[5]=-1;
	x1[6]=0;x2[6]=-1;
	x1[7]=x2[7]=-1;
}

int main()
{
	citire();
	compute();
	afisare();
	return 0;
}