Cod sursa(job #117965)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 22 decembrie 2007 21:23:33
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<stdio.h>
#include<stdlib.h>
long int n,m,a[503][503],si,sj,fi,fj,i,j,ih[200000],jh[200000],dh[200000],ch[20000],
lh,i1,j1,d1,c1,i2,j2,d2,c2,cbest[503][503][8],aux,k,
pr[8][8],sol,di[8],dj[8],dest[8][5],cost[8][5];
void swap(long int ii1,long int ii2);
void heapdown(long int ic,long int nc);
void heapup(long int ic);
int main()
{
	for(i=0;i<=6;i++)
	for(j=i+1;j<=7;j++)
	{ pr[i][j]=j-i;if(pr[i][j]>4)pr[i][j]=8-pr[i][j];pr[j][i]=pr[i][j];}
	di[0]=-1;di[1]=-1;di[2]= 0;di[3]= 1;
	di[4]= 1;di[5]=-1;di[6]= 0;di[7]=-1;
	dj[0]= 0;dj[1]= 1;dj[2]= 1;dj[3]= 1;
	dj[4]= 0;dj[5]= 1;dj[6]=-1;dj[7]=-1;
	for(i=0;i<=7;i++)
	{ dest[i][0]=i;cost[i][0]=0;
	  dest[i][1]=i+1;if(dest[i][1]>=8)dest[i][1]-=8;cost[i][1]=1;
	  dest[i][2]=i-1;if(dest[i][2]<0)dest[i][2]+=8;cost[i][2]=1;
	  dest[i][3]=i+2;if(dest[i][3]>=8)dest[i][3]-=8;cost[i][3]=2;
	  dest[i][4]=i-2;if(dest[i][4]<0)dest[i][4]+=8;cost[i][4]=2;
	}
	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);
	for(i=1;i<=n;i++)
	  for(j=1;j<=m;j++)
	   { fscanf(f,"%ld",&a[i][j]);
	     for(k=0;k<=7;k++)
	     cbest[i][j][k]=20000000;
           }
	for(i=0;i<=n+1;i++)
	 {a[i][0]=1;a[i][m+1]=1;}
	for(j=0;j<=m+1;j++)
	 {a[0][j]=1;a[n+1][j]=1;}
	for(i=1;i<=8;i++)
	{ ih[i]=si;jh[i]=sj;dh[i]=i-1;ch[i]=0;}
	lh=8;
	while(lh)
	{  if(ih[1]==fi&&jh[1]==fj)
	    { fprintf(g,"%ld\n",ch[1]);fcloseall();return 0;}
	   i1=ih[1];j1=jh[1];d1=dh[1];c1=ch[1];
	   swap(1,lh);lh--;if(lh)heapdown(1,lh);
	   if(cbest[i1][j1][d1]>c1)
	   { cbest[i1][j1][d1]=c1;
	     for(i=0;i<=4;i++)
	     {    d2=dest[d1][i];
		  i2=i1+di[d2];
		  j2=j1+di[d2];
		  c2=c1+cost[d1][i];
		  if(!a[i2][j2])
		  { lh++;
		    dh[lh]=d2;ih[lh]=i2;jh[lh]=j2;ch[lh]=c2;
		    heapup(lh);
		  }
	      }
	   }
	}
	fprintf(g,"-1\n",sol);
	fcloseall();
	return 0;
}
void swap(long int ii1,long int ii2)
{
	aux=ih[ii1];ih[ii1]=ih[ii2];ih[ii2]=aux;
	aux=jh[ii1];jh[ii1]=jh[ii2];jh[ii2]=aux;
	aux=dh[ii1];dh[ii1]=dh[ii2];dh[ii2]=aux;
	aux=ch[ii1];ch[ii1]=ch[ii2];ch[ii2]=aux;
}
void heapdown(long int ic,long int nc)
{
	long int is,is1;
	is=2*nc;is1=2*ic+1;
	if(ic>nc) return;
	if(ic<nc) if(ch[is1]<ch[is])is=is1;
	if(ch[ic]>ch[is]){swap(ic,is);heapdown(is,nc);}
}
void heapup(long int ic)
{
	if(ic==1)return;
	if(ch[ic]>=ch[ic/2])return;
	swap(ic,ic/2);
	heapup(ic/2);
}