Cod sursa(job #6520)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 19 ianuarie 2007 22:43:44
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <cstdio>

#define FIN "car.in"
#define FOUT "car.out"
#define MAX 600
#define inf 0x3f3f3f
#define h_x (P->x)
#define h_y (P->y)
#define t_x (h_x+dx[i])
#define t_y (h_y+dy[i])

struct node {
	long x, y;
	node *next;
} S, F;
node *P, *U;

long dx[] = {-1, -1, 0, 1, 1, 1, 0, -1},
	 dy[] = {0, 1, 1, 1, 0, -1, -1, -1};
long rot[8][8] = {
	{0, 1, 2, 3, 4, 3, 2, 1},
	{1, 0, 1 ,2, 3, 4, 3, 2},
	{2, 1, 0, 1, 2, 3, 4, 3},
	{3, 2, 1, 0, 1, 2, 3, 4},
	{4, 3, 2, 1, 0, 1, 2, 3},
	{3, 4, 3, 2, 1, 0, 1, 2},
	{2, 3, 4, 3, 2, 1, 0, 1},
	{1, 2, 3, 4, 3, 2, 1, 0}
};

long Dir[MAX][MAX], C[MAX][MAX];
long A[MAX][MAX], Queued[MAX][MAX];
long N,M, i,j;

inline void add(long x, long y) {
	node *temp = new node;
	Queued[x][y] = 1;
	temp -> x = x;
	temp -> y = y;
	temp -> next = 0;
	U -> next = temp;
	U=temp;
}

int msb( long x ) { // most significant byte
	long i;
	for ( i=0; i<8; ++i )
		if ( 1<<i == x ) 
			return i;
//	return -1;
}

int main() {
	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &N, &M);
	scanf("%ld %ld %ld %ld", &S.x, &S.y, &F.x, &F.y);
	for (i=1; i<=N; ++i)
		for (j=1; j<=M; ++j)
			scanf("%ld", A[i]+j);
	fclose(stdin);

	// init
	for (i=1; i<=N; ++i)
		for (j=1; j<=M; ++j)
			if ( !A[i][j] ) 
				C[i][j] = inf;
	C[S.x][S.y] = 0;
	// lee
	P = new node; U=P;
	for (i=0; i<8; ++i)
		if ( C[S.x+dx[i]][S.y+dy[i]] == inf) {
			add(S.x+dx[i], S.y+dy[i]);
			C[S.x+dx[i]][S.y+dy[i]] = 0;
			Dir[S.x+dx[i]][S.y+dy[i]] = 1<<i;
		}
	while ( P ) {
		for (i=0; i<8; ++i) 
			if ( A[t_x][t_y] == 0 )
				for (j=0; j<8; ++j)
					if ( Dir[h_x][h_y] & (1<<j) ) {
						long lval = C[h_x][h_y] + rot[ msb(Dir[h_x][h_y] & (1<<j)) ][i];
						if ( C[t_x][t_y] > lval ) {
							if ( !Queued[t_x][t_y] )
								add(t_x, t_y);
							C[t_x][t_y] = lval;
							Dir[t_x][t_y] = 0;
						} 
						if ( C[t_x][t_y] == lval ) {
							Dir[t_x][t_y] |= 1<<i;
						}
		}

		node *temp = P;
		Queued[h_x][h_y] = 0;
		P = P->next;
		delete temp;
	}

	// debug
/*
	for (i=1; i<=N; ++i) {
		for (j=1; j<=M; ++j)
			printf("%5ld", C[i][j]);
		printf("\n");
	}
*/


	freopen(FOUT, "w", stdout);
	if ( C[F.x][F.y]==inf || C[F.x][F.y] == 0 )
		printf("%ld\n", C[F.x][F.y]);
	else
		printf("-1\n");
	fclose(stdout);
	return 0;
}