Cod sursa(job #80025)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 25 august 2007 15:28:28
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<stdio.h>
#include<stdlib.h>
struct nod{
long int x;
long int y;
long int d;
long int c;
nod *next;
};
nod *prim,*ultim,*paux;
long int m,n,i,j,xi,yi,xf,yf,oc[502][502],h,infinit,k,s[8][502][502],sol,
co[8][8],x0,y0,d0,c0,x1,y1,d1,c1;
void pune0();
void pune(long int xx,long int yy,long int dd,long int cc);
int main()
{
	FILE *f,*g;f=fopen("car.in","r");g=fopen("car.out","w");
	fscanf(f,"%ld%ld",&m,&n);
	fscanf(f,"%ld%ld",&xi,&yi);
	fscanf(f,"%ld%ld",&xf,&yf);
	infinit=2000000000;
	for(i=1;i<=m;i++)for(j=1;j<=n;j++){ fscanf(f,"%ld",&oc[i][j]);for(k=0;k<=7;k++)s[k][i][j]=infinit;}
	for(i=0;i<=7;i++)s[i][xi][yi]=0;
	co[0][1]=1;co[0][2]=2;co[0][3]=3;co[0][4]=4;co[0][5]=3;co[0][6]=2;co[0][7]=1;
	for(i=1;i<=7;i++){ for(j=1;j<=7;j++)co[i][j]=co[i-1][j-1];co[i][0]=co[i-1][7];}
	for(i=0;i<=m+1;i++){ oc[i][0]=1;oc[i][n+1]=1;}for(j=0;j<=n+1;j++){ oc[0][j]=1;oc[m+1][j]=1;}
	sol=infinit;
	prim=new nod;
	ultim=new nod;
	prim->x=xi;prim->y=yi;prim->d=0;prim->c=0;prim->next=0;ultim=prim;
	for(i=1;i<=7;i++) pune0();
	while(prim)
	{       x0=prim->x;y0=prim->y;d0=prim->d;c0=prim->c;
		if(c0<=s[d0][x0][y0]&&c0<sol)
		{
			x1=x0-1;y1=y0;
			if(!oc[x1][y1]){d1=0;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0-1;y1=y0+1;
			if(!oc[x1][y1]){d1=1;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0;  y1=y0+1;
			if(!oc[x1][y1]){d1=2;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0+1;y1=y0+1;
			if(!oc[x1][y1]){d1=3;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0+1;y1=y0;
			if(!oc[x1][y1]){d1=4;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0+1;y1=y0-1;
			if(!oc[x1][y1]){d1=5;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0;  y1=y0-1;
			if(!oc[x1][y1]){d1=6;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
			x1=x0-1;y1=y0-1;
			if(!oc[x1][y1]){d1=7;c1=c0+co[d1][d0];if(c1<sol)if(c1<s[d1][x1][y1])pune(x1,y1,d1,c1);}
		}
		paux=new nod;paux=prim;prim=prim->next;free(paux);
	}

	fprintf(g,"%ld\n",sol);
	fcloseall();
	return 0;
}
void pune0()
{
	nod *pp;
	pp=new nod;
	pp->x=xi;pp->y=yi;pp->d=i;pp->c=0;pp->next=0;
	ultim->next=pp;ultim=pp;
}
void pune(long int xx,long int yy,long int dd,long int cc)
{
	nod *ppp;
	if(xx==xf&&yy==yf){sol=cc;return;}
	s[dd][xx][yy]=cc;
	ppp=new nod;
	ppp->x=xx;ppp->y=yy;ppp->d=dd;ppp->c=cc;ppp->next=0;
	ultim->next=ppp;ultim=ppp;
}