Cod sursa(job #22346)

Utilizator t30Rosu Teodor t30 Data 26 februarie 2007 11:20:27
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<stdio.h>
typedef struct list { long x; list *d; } list;
list *l[1000100];
list *co[1000100];
int xx[8]={-1,-1,0,1,1,1,0,-1};
int yy[8]={0,1,1,1,0,-1,-1,-1};
int cpl[8]={4,5,6,7,0,1,2,3};
long d[2100000],n,m,sx,sy,ex,ey,v[510][510],sol;

void add(long c,long x)
{
   list *p=new list;
   d[x]=1;
   p->x=x;
   p->d=NULL;
   if(!co[c]){
	p->d=l[c];
	l[c]=p;
   }
   else  co[c]->d=p;
   co[c]=p;


}


void READ()
{  int i,j;
   FILE *f;
   f=fopen("car.in","r");
   fscanf(f,"%d %d",&n,&m);
   fscanf(f,"%d %d %d %d",&sx,&sy,&ex,&ey);
   for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
	fscanf(f,"%d",&v[i][j]);
   for(i=0;i<8;i++)
      add(0,(sx*51+sy)*8+i);

   fclose(f);
}

long SOLVE()
{  long c=0,x,y,X,Y,k,i;
   list *p;
   while(l[c]){
	p=l[c];
	while(p){
	  k=p->x%8;
	  y=(p->x/8)%51;
	  x=(p->x/8)/51;
	  X=x+xx[k];
	  Y=y+yy[k];
	  if(X>0 && X<=n && Y>0 && Y<=m && v[X][Y]==0 && !d[(X*51+Y)*8+k])
		{ add(c,(X*51+Y)*8+k);
		  d[(X*51+Y)*8+cpl[k]]=1;
		}
	p=p->d;
	if(x==ex && y==ey) return c;
	}
	p=l[c];
	while(p){
		i=p->x%8;
		k=(long)(p->x/8)*8+(i+1)%8;
		if(!d[k]) { d[k]=1; add(c+1,k); }
		k=(long)(p->x/8)*8+(i+7)%8;
		if(!d[k]) { d[k]=1; add(c+1,k); }
	p=p->d;
	}
   c++;
   }
return -1;
}

void PRINT()
{
   FILE *g;
   g=fopen("car.out","w");
   fprintf(g,"%ld\n",sol);
   fclose(g);
}

int main()
{
  READ();
  sol=SOLVE();
  PRINT();
return 0;
}