Cod sursa(job #570287)

Utilizator rootsroots1 roots Data 2 aprilie 2011 19:55:56
Problema Car Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <stdio.h>

#define Dim 505

int A[Dim][Dim];
int dx[8]={-1,0,1,1,1,0,-1,-1};
int dy[8]={-1,-1,-1,0,1,1,1,0};
int m[8][3][3];

struct queue
{
	int x,y,d;
	queue *link;
}*C1,*C2,*aux;

void add(queue *&C,int x,int y,int d)
{
	queue *p;

	p=new queue;
	p->x=x;
	p->y=y;
	p->d=d;
	p->link=C;
	C=p;
}

int main()
{
	m[0][0][0]=0; m[0][0][1]=1; m[0][0][2]=2;
	m[0][1][0]=1; m[0][1][1]=5; m[0][1][2]=3;
	m[0][2][0]=2; m[0][2][1]=3; m[0][2][2]=4;

	m[1][0][0]=1; m[1][0][1]=2; m[1][0][2]=3;
	m[1][1][0]=0; m[1][1][1]=5; m[1][1][2]=4;
	m[1][2][0]=1; m[1][2][1]=2; m[1][2][2]=3;

	m[2][0][0]=2; m[2][0][1]=3; m[2][0][2]=4;
	m[2][1][0]=1; m[2][1][1]=5; m[2][1][2]=3;
	m[2][2][0]=0; m[2][2][1]=1; m[2][2][2]=2;

	m[3][0][0]=3; m[3][0][1]=4; m[3][0][2]=3;
	m[3][1][0]=2; m[3][1][1]=5; m[3][1][2]=2;
	m[3][2][0]=1; m[3][2][1]=0; m[3][2][2]=1;

	m[4][0][0]=4; m[4][0][1]=3; m[4][0][2]=2;
	m[4][1][0]=3; m[4][1][1]=5; m[4][1][2]=1;
	m[4][2][0]=2; m[4][2][1]=1; m[4][2][2]=0;

	m[5][0][0]=3; m[5][0][1]=2; m[5][0][2]=1;
	m[5][1][0]=4; m[5][1][1]=5; m[5][1][2]=0;
	m[5][2][0]=3; m[5][2][1]=2; m[5][2][2]=1;

	m[6][0][0]=2; m[6][0][1]=1; m[6][0][2]=0;
	m[6][1][0]=3; m[6][1][1]=5; m[6][1][2]=1;
	m[6][2][0]=4; m[6][2][1]=3; m[6][2][2]=2;

	m[7][0][0]=1; m[7][0][1]=0; m[7][0][2]=1;
	m[7][1][0]=2; m[7][1][1]=5; m[7][1][2]=2;
	m[7][2][0]=3; m[7][2][1]=4; m[7][2][2]=3;

	int M,N,x1,x2,y1,y2,x,y,i,j,end,d,cost;

	freopen("car.in","r",stdin);

	scanf("%d%d",&M,&N);
	scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

	for(i=1;i<=M;i++)
		for(j=1;j<=N;j++)
		{
			scanf("%d",&x);
			if(x==1) A[i][j]=-1;
			else A[i][j]=0;
		}

	A[x1][y1]=1;
	C1=NULL;
	for(i=0;i<8;i++)
		if((0<x1+dx[i])&&(x1+dx[i]<=M)&&(0<y1+dy[i])&&(y1+dy[i]<=N))
			if(A[x1+dx[i]][y1+dy[i]]==0)
				add(C1,x1,y1,i);

	C2=NULL;
	end=0;
	while(!end)
	{
		while(C1)
		{
			x=C1->x;
			y=C1->y;
			d=C1->d;
			aux=C1;
			C1=C1->link;
			delete aux;

			for(i=0;i<8;i++)
				if((0<x+dx[i])&&(x+dx[i]<=M)&&(0<y+dy[i])&&(y+dy[i]<=N))
				{
					cost=A[x][y];
					cost+=m[d][dx[i]+1][dy[i]+1];
					if(A[x+dx[i]][y+dy[i]]==0)
					{
						A[x+dx[i]][y+dy[i]]=cost;
						add(C2,x+dx[i],y+dy[i],i);
					}
				}
		}
		if(C2==NULL)
		{
			end=0;
			break;
		}
		C1=C2;
		C2=NULL;
	}

	freopen("car.out","w",stdout);

	printf("%d\n",A[x2][y2]-1);

	return 0;
}