Cod sursa(job #179728)

Utilizator razvi9Jurca Razvan razvi9 Data 16 aprilie 2008 11:55:15
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<cstdio>
#include<cstring>
int n,m,inc,fin,a[501][501],cost[501][501],i,j,st,dr,curba[9][9];
const int inf=0x7f7f7f7f;
struct list{int i,j,dir,cost;};
list l[500*500*10+1];
inline void go(int x,int y,int c,int dir)
{
	if(a[x][y]==1) return;
	if(x<1 || y<1 || x>n || y>m) return;
	if(cost[x][y]<c) return;
	cost[x][y]=c;
	l[++dr].i=x;
	l[dr].j=y;
	l[dr].dir=dir;
	l[dr].cost=c;

}
int abs(int x)
{
	if(x<0) return -x;
	return x;
}
int _cost(int d1,int d2)
{
	int x=abs(d2-d1);
	if(x<=4) return x;
	return 8-x;
}
/*
812
7*3
654
*/
inline void goall(int x,int y,int d,int c)
{
	go(x+1,y,c+curba[1][d],1);
	go(x+1,y-1,c+curba[2][d],2);
	go(x,y-1,c+curba[3][d],3);
	go(x-1,y-1,c+curba[4][d],4);
	go(x-1,y,c+curba[5][d],5);
	go(x-1,y+1,c+curba[6][d],6);
	go(x,y+1,c+curba[7][d],7);
	go(x+1,y+1,c+curba[8][d],8);

}
inline void bf()
{
	int dir;
	memset(cost,0x7f,sizeof(cost));
	i=inc/1000;j=inc%1000;
	st=0;dr=-1;
	for(int k=1;k<=8;k++)
		go(i,j,0,k);
	while(st<=dr)
	{
		goall(l[st].i,l[st].j,l[st].dir,l[st].cost);
		st++;
	}

end:
	if(cost[fin/1000][fin/1000]==inf)
		cost[fin/1000][fin/1000]=-1;
}
int main()
{
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d %d",&n,&m);
	scanf("%d %d",&i,&j);inc=i*1000+j;
	scanf("%d %d",&i,&j);fin=i*1000+j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(i=1;i<=8;i++)
		for(j=1;j<=8;j++)
			curba[i][j]=_cost(i,j);
	bf();
	printf("%d",cost[fin/1000][fin%1000]);
	fclose(stdout);
	return 0;
}