Cod sursa(job #9076)

Utilizator t30Rosu Teodor t30 Data 26 ianuarie 2007 17:04:20
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include<stdio.h>
#define MAX 75000
typedef struct nod { long x,c; nod *d; } nod;
nod *v[2000100];

long n,m,sx,sy,fx,fy,a[51][51];
long d[2000100],w[2000100],e[2000100],nr,tg,min;

long cod(long x,long y,long k)
{return((x-1)*m+(y-1))*8+k; }

void add(long x,long y,long c)
{ nod *pp;
  pp=new nod;
  pp->x=y;
  pp->c=c;
  pp->d=v[x];
  v[x]=pp;
}

void READ()
{  long i,j,k;
	FILE *f;
	f=fopen("car.in","r");
	fscanf(f,"%ld %ld",&n,&m);
	fscanf(f,"%ld %ld %ld %ld",&sx,&sy,&fx,&fy);
	for(i=1;i<=n;i++)
	  for(j=1;j<=m;j++)
		 fscanf(f,"%ld",&a[i][j]);

	for(i=1;i<=n;i++)
	  for(j=1;j<=m;j++)
		for(k=0;k<8;k++)
		{ add(cod(i,j,k),cod(i,j,(k+1)%8),1);
		  add(cod(i,j,(k+1)%8),cod(i,j,k),1);
		}
	for(i=1;i<=n;i++)
	  for(j=1;j<=m;j++)
		 if(a[i][j]==0)
		 { if(i>1 && a[i-1][j]==0) { add(cod(i,j,0),cod(i-1,j,0),0); add(cod(i-1,j,4),cod(i,j,4),0);  }
			if(j>1 && a[i][j-1]==0) { add(cod(i,j,6),cod(i,j-1,6),0); add(cod(i,j-1,2),cod(i,j,2),0);  }
			if(i<n && j>1 && a[i+1][j-1]==0) { add(cod(i,j,5),cod(i+1,j-1,5),0); add(cod(i+1,j-1,1),cod(i,j,1),0);  }
			if(i>1 && j>1 && a[i-1][j-1]==0) { add(cod(i,j,7),cod(i-1,j-1,7),0); add(cod(i-1,j-1,3),cod(i,j,3),0);  }
		 }
}
void swap(long &x,long &y)
{
  long z=x; x=y; y=z;
}


void urca(long x)
{
  while(x/2!=0 && d[x]<d[x/2])
  {
	 swap(d[x],d[x/2]);
	 e[w[x]]=x/2;
	 e[w[x/2]]=x;
	 swap(w[x],w[x/2]);
	 x=x/2;
  }
}

void coboara(long x)
{
  m=x;
  if(2*x<=nr && d[2*x]<d[m]) m=2*x;
  if(2*x+1<=nr && d[2*x+1]<d[m])  m=2*x+1;
  if(m!=x) {  swap(d[x],d[m]); e[w[x]]=m; e[w[m]]=x; swap(w[x],w[m]);  coboara(m);}
}



void build()
{ long i;
  for(i=nr/2;i>=1;i--)
  {
	 if(2*i<=nr && d[2*i]<d[i]) { swap(d[i],d[2*i]); e[w[i]]=2*i;e[w[2*i]]=i; swap(w[i],w[2*i]); coboara(2*i); }
	 if(2*i+1<=nr && d[2*i+1]<d[i]) { swap(d[i],d[2*i+1]); e[w[i]]=2*i+1;e[w[2*i+1]]=i; swap(w[i],w[2*i+1]); coboara(2*i+1); }
  }
}

void SOLVE()
{
 long i,x;
 nod *p;
 nr=cod(n,m,7)+1;
 tg=cod(fx,fy,0);

 min=MAX;

 for(i=0;i<nr;i++)
 {	d[i+1]=MAX;
	w[i+1]=i;
	e[i]=i+1;}
 for(i=0;i<8;i++)
	d[cod(sx,sy,i)+1]=0;
 build();
 for(;nr>0 && d[1]!=MAX;)
 {
	if(tg<=w[1] && w[1]<=tg+7 && min>d[1]) min=d[1];
	x=w[1];
	p=v[x];
	while(p)
	{
	  if(d[1]+ p->c <d[ e[p->x] ]) {d[ e[p->x] ]=d[1]+p->c; urca(e[p->x]); }
	  p=p->d;
	}
	d[1]=d[nr];
	w[1]=w[nr];
	e[w[1]]=1;
	nr--;
	coboara(1);
 }

}

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

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