Cod sursa(job #118227)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 23 decembrie 2007 20:08:51
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<stdio.h>
long int n,m,si,sj,spoz,fi,fj,fpoz,i,j,x,k,stare[2200000],
m0[8],m1[8],m2[8],aa,ist,fst,ipo,fpo,cc,*L1,*L2,LL1[2200000],LL2[2200000],
t1,t2,tt1,dir,x0,x1,x2,*La;
void init();
int main()
{
	FILE *f,*g;f=fopen("car.in","r");g=fopen("car.out","w");
	fscanf(f,"%ld%ld",&n,&m);
	fscanf(f,"%ld%ld",&si,&sj);
	fscanf(f,"%ld%ld",&fi,&fj);
	init();
	j=0;for(i=0;i<=n+1;i++){x=4096*i+8*j;for(k=x;k<=x+7;k++)stare[k]=3;}
	j=m+1;for(i=0;i<=n+1;i++){x=4096*i+8*j;for(k=x;k<=x+7;k++)stare[k]=3;}
	i=0;for(j=0;j<=m+1;j++){x=4096*i+8*j;for(k=x;k<=x+7;k++)stare[k]=3;}
	i=n+1;for(j=0;j<=m+1;j++){x=4096*i+8*j;for(k=x;k<=x+7;k++)stare[k]=3;}
	for(i=1;i<=n;i++)for(j=1;j<=m;j++)
	 {fscanf(f,"%ld\n",&aa);if(aa){x=4096*i+8*j;for(k=x;k<=x+7;k++)stare[k]=3;}}
	ist=4096*si+8*sj;fst=4096*fi+8*fj;
	ipo=ist/8;fpo=fst/8;if(ipo==fpo){fprintf(g,"0\n");fcloseall();return 0;}
	cc=0;
	L1=&LL1[0];L2=&LL2[0];
	for(i=0;i<=7;i++){t1++;L1[t1]=ist+i;}
	while(t1)
	{       tt1=0;
		for(i=1;i<=t1;i++)
		{ if(stare[L1[i]]==3)continue;
		  if((L1[i]/8)==fpo)
		   {fprintf(g,"%ld\n",cc);fcloseall();return 0;}
		  tt1++;L1[tt1]=L1[i];stare[L1[i]]=2;
		}
		t1=tt1;
		if(!t1){fprintf(g,"-1\n");fcloseall();return 0;}
		for(i=1;i<=t1;i++)
		{ x=L1[i];dir=x%8;
		  x0=x+m0[dir];
		  if(x0/8==fpo)
		  if(stare[x0]<2){stare[x0]=2;t1++;L1[t1]=x0;}
		  x1=x+m1[dir];if(!stare[x1]){stare[x1]=1;t2++;L2[t2]=x1;}
		  x2=x+m2[dir];if(!stare[x2]){stare[x2]=1;t2++;L2[t2]=x2;}
		  stare[x]=3;
		}
		for(i=fst;i<=fst+7;i++)
		if(stare[i]==3){fprintf(g,"%ld\n",cc);fcloseall();return 0;}
		t1=t2;t2=0;La=L1;L1=L2;L2=La;cc++;
	}

	fprintf(g,"-1\n");
	fcloseall();
	return 0;
}
void init()
{
	m0[0]=-4096;m1[0]=7;m2[0]=1;
	m0[1]=-4088;m1[1]=-1;m2[1]=1;
	m0[2]=8;m1[2]=-1;m2[2]=1;
	m0[3]=4104;m1[3]=-1;m2[3]=1;
	m0[4]=4096;m1[4]=-1;m2[4]=1;
	m0[5]=4088;m1[5]=-1;m2[5]=1;
	m0[6]=-8;m1[6]=-1;m2[6]=1;
	m0[7]=-4104;m1[7]=-1;m2[7]=-7;
}