Cod sursa(job #504261)

Utilizator crushackPopescu Silviu crushack Data 27 noiembrie 2010 11:34:57
Problema Car Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <stdio.h>
#include <queue>
#define NMax 505
using namespace std;

const char IN[]="car.in",OUT[]="car.out";
const int d[8][2]={ {-1,-1} , {-1,0} , {-1,1} , {0,1} , {1,1} , {1,0} , {1,-1} , {0,-1}};

int N,M;
bool a[NMax][NMax];
int T[NMax][NMax][8];
struct point
{ int x,y;} start,finish;
struct poz
{ int x,y,d;};

int abs(int x)
{
	return (x<0) ? -x : x;
}

int Lee(point start , point finish)
{
	int i;
	queue<poz> qu;
	poz x;
	
	x.x=start.x;x.y=start.y; x.d=0;
	for (i=0;i<8;i++) T[x.x][x.y][i]=1;
	for (i=0;i<8;i++)
	{
		poz tmp={x.x+d[i][0],x.y+d[i][1],i};
		if ( !a[tmp.x][tmp.y] )
		{
			qu.push(tmp);
			T[tmp.x][tmp.y][i]=1;
		}
	}
	while (!qu.empty())
	{
		x=qu.front();
		qu.pop();
		for (i=0;i<8;i++)
		{
			poz tmp={x.x+d[i][0],x.y+d[i][1],i};
			if ( ! a[tmp.x][tmp.y] &&(!T[tmp.x][tmp.y][i] || T[tmp.x][tmp.y][i]>T[x.x][x.y][x.d]+abs(i-x.d)))
			{
				qu.push(tmp);
				T[tmp.x][tmp.y][i]=T[x.x][x.y][x.d]+abs(i-x.d);
			}
		}
	}
	int min=-1;
	for (i=0;i<8;i++)
		if ( (min<0 || T[finish.x][finish.y][i]<min) && T[finish.x][finish.y][i])
			min=T[finish.x][finish.y][i];
	return (min>0) ? min-1 : min;
}

int main()
{
	int i,j,x;
	freopen(IN,"r",stdin);
	scanf("%d%d%d%d%d%d",&N,&M,&start.x,&start.y,&finish.x,&finish.y);
	for (i=0;i<=M+1;i++) a[0][i]=a[N+1][i]=1;
	for (i=1;i<=N;i++){
		a[i][0]=a[i][N+1]=1;
		for (j=1;j<=M;j++)
			scanf("%d",&x),
			a[i][j]= x!=0 ;
	}
	fclose(stdin);
	/*for (i=0;i<=N+1;i++){
		for (j=0;j<=M+1;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}*/
	
	freopen(OUT,"w",stdout);
	printf("%d\n",Lee(start,finish));
	fclose(stdout);
	return 0;
}