Cod sursa(job #118175)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 23 decembrie 2007 13:21:50
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include<stdio.h>
long int n,m,p3,u3,p9,u9,p12,u12,si,sj,spoz,fi,fj,fpoz,i,j,aa,a[270000],
ccost,top1,top2,bottom1,*s1,suport1[2000000],*s2,suport2[2000000],csta,cpoz,
nsta,npoz,vizsta[2100000],coststa[2100000],cdir,*s3;
int main()
{
	FILE *f,*g;f=fopen("car.in","r");g=fopen("car.out","w");
	fscanf(f,"%ld%ld",&n,&m);
	p3=1<<3;p9=1<<9;p12=1<<12;
	u3=p3-1;u9=p9-1;u12=p12-1;
	//codificare pozitie poz=i<<9+j;
	//decodificare pozitie i=poz>>9;j=poz&u9;
	//codificare stare sta=i<<12+j<<3+d;
	//decodificare stare i=sta>>12;j=(sta>>3)&u9;d=sta&&u3
	//codificare stare pozitie sta=poz<<3+d;
	//decodificare stare pozitie poz=sta>>3;d=sta&&u3;
	fscanf(f,"%ld%ld",&si,&sj);spoz=si<<9+sj;
	fscanf(f,"%ld%ld",&fi,&fj);fpoz=fi<<9+fj;
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)
	{fscanf(f,"%ld",&aa);a[i<<9+j]=aa;}
	for(i=0;i<=n+1;i++)
	{a[i<<9]=1;a[i<<9+m+1]=1;}
	for(j=0;j<=m+1;j++){a[j]=1;a[(n+1)<<9+j]=1;}
	ccost=0;for(i=0;i<=7;i++){top1++;suport1[top1]=spoz<<3+i;}
	s1=&suport1[0];s2=&suport2[0];
	while(top1)
	{
	  top2=0;
	  for(bottom1=1;bottom1<=top1;bottom1++)
	  { csta=s1[bottom1];cpoz=csta>>3;
	    if(cpoz==fpoz){fprintf(g,"%ld\n",ccost);fcloseall();return 0;}
	    if(!vizsta[csta])
	     { coststa[csta]=ccost;vizsta[csta]=1;
	       cdir=csta&&u3;
	       if(cdir==0)
	       {nsta=csta-p12;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta+7;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==1)
	       {nsta=csta-p12+p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==2)
	       {nsta=csta+p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==3)
	       {nsta=csta+p12+p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==4+p12)
	       {nsta=csta-p12;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==5)
	       {nsta=csta+p12-p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==6)
	       {nsta=csta-p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta+1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	       else
	       if(cdir==7)
	       {nsta=csta-p12-p3;npoz=nsta>>3;
		if(!a[npoz]&&!vizsta[nsta]){top1++;s1[top1]=nsta;}
		nsta=csta-7;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}
		nsta=csta-1;if(!vizsta[nsta]){top2++;s2[top2]=nsta;}}
	     }
	  }
	  top1=top2;s3=s1;s1=s2;s2=s3;ccost++;
	}
	fprintf(g,"-1\n");
	fcloseall();
	return 0;
}