Cod sursa(job #129613)

Utilizator ThomasFMI Suditu Thomas Thomas Data 29 ianuarie 2008 19:43:26
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<stdio.h>
#include<stdlib.h>
struct nod{long int stare;nod *next;};
long int n,m,si,sj,fi,fj,vizp[270000],poz0,sta0,dir0,i0,j0,i,j,aa,
vizs[2200000],pozf,csol,cc,poz1,sta1,dir1,i1,j1,ddi[8],ddj[8],
dirl[8],dirr[8],pozs;
nod *p0,*u0,*pp,*p1,*u1;
void init();
void scoate0();
void pune0(long int sss);
void pune1(long int sss);
void schimba();
int main()
{
	FILE *f,*g;f=fopen("car.in","r");g=fopen("car.out","w");
	fscanf(f,"%ld%ld",&n,&m);
	if(n==0||m==0) {fprintf(g,"-1\n");fcloseall();return 0;}
	fscanf(f,"%ld%ld",&si,&sj);
	fscanf(f,"%ld%ld",&fi,&fj);
	if(si==fi&&sj==fj) { fprintf(g,"0\n");fcloseall();return 0;}
	for(i=0;i<=n+1;i++)
	{ poz0=i<<9;vizp[poz0]=1;
	  poz0=(i<<9)+m+1;vizp[poz0]=1;
	}
	for(j=0;j<=m+1;j++)
	{ poz0=j;vizp[poz0]=1;
	  poz0=((n+1)<<9)+j;vizp[poz0]=1;
	}
	for(i=1;i<=n;i++)
	 for(j=1;j<=m;j++)
	 { fscanf(f,"%ld",&aa);
	   poz0=(i<<9)+j;vizp[poz0]=aa;
	 }
	init();
	while(p0->next!=u0)
	{
		pp=p0->next;sta0=pp->stare;poz0=sta0>>3;dir0=sta0&7;i0=poz0>>9;j0=poz0&511;
		if(vizp[poz0]){ pp=0;scoate0();}
		else
		if(vizs[sta0]){pp=0;scoate0();}
		else
		{ if(poz0==pozf)
		  {csol=cc-1;fprintf(g,"%ld\n",csol);fcloseall();return 0;}
		  vizs[sta0]=1;
		  pp=0;scoate0();
		  i1=i0+ddi[dir0];j1=j0+ddj[dir0];dir1=dir0;
		  poz1=(i1<<9)+j1;sta1=(poz1<<3)+dir1;
		  if(!vizp[poz1])
		   if(!vizs[sta1])pune0(sta1);
		  i1=i0;j1=j0;dir1=dirl[dir0];
		  poz1=(i1<<9)+j1;sta1=(poz1<<3)+dir1;
		  if(!vizp[poz1])
		   if(!vizs[sta1])pune1(sta1);
		  i1=i0;j1=j0;dir1=dirr[dir0];
		  poz1=(i1<<9)+j1;sta1=(poz1<<3)+dir1;
		  if(!vizp[poz1])
		   if(!vizs[sta1])pune1(sta1);
		}
		if(p0->next==u0)schimba();
	 }
	fprintf(g,"-1\n");
	fcloseall();
	return 0;
}
void init()
{
    ddi[0]=-1;ddj[0]=0;dirl[0]=7;dirr[0]=1;
    ddi[1]=-1;ddj[1]=1;dirl[1]=0;dirr[1]=2;
    ddi[2]=0;ddj[2]=1;dirl[2]=1;dirr[2]=3;
    ddi[3]=1;ddj[3]=1;dirl[3]=2;dirr[3]=4;
    ddi[4]=1;ddj[4]=0;dirl[4]=3;dirr[4]=5;
    ddi[5]=1;ddj[5]=-1;dirl[5]=4;dirr[5]=6;
    ddi[6]=0;ddj[6]=-1;dirl[6]=5;dirr[6]=7;
    ddi[7]=-1;ddj[7]=-1;dirl[7]=6;dirr[7]=0;
    p0=new nod;u0=new nod;p0->next=u0;
    p1=new nod;u1=new nod;p1->next=u1;
    cc=1;pozs=(si<<9)+sj;pozf=(fi<<9)+fj;
    for(dir0=0;dir0<=7;dir0++){sta0=(pozs<<3)+dir0;pune0(sta0);}
}
void pune0(long int sss)
{
	nod *paux;
	paux=new nod;
	paux->stare=sss;
	paux->next=p0->next;
	p0->next=paux;
}
void pune1(long int sss)
{
	nod *paux;
	paux=new nod;
	paux->stare=sss;
	paux->next=p1->next;
	p1->next=paux;
}
void scoate0()
{
	nod *paux;
	paux=p0->next;
	if(paux==u0) return;
	p0->next=paux->next;
	free(paux);
}
void schimba()
{       nod *paux;
	cc=cc+1;
	paux=p0;p0=p1;p1=paux;
	paux=u0;u0=u1;u1=paux;
}