Cod sursa(job #179730)

Utilizator razvi9Jurca Razvan razvi9 Data 16 aprilie 2008 11:57:42
Problema Car Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<cstdio>
#include<cstring>
#include<deque>
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 aux;
std::deque<list> l;
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;
	aux.i=x;
	aux.j=y;
	aux.dir=dir;
	aux.cost=c;
	l.push_back(aux);
}
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;
	for(int k=1;k<=8;k++)
		go(i,j,0,k);
	while(l.size())
	{
		aux=l[0];l.pop_front();
		goall(aux.i,aux.j,aux.dir,aux.cost);
	}

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;
}