Cod sursa(job #204838)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 27 august 2008 14:01:17
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<stdio.h>
#define N 507
#define M 8
#define D 7
#define Y 4090
#define X 2093060

int v[N][N], min[M][N][N], car[N*N*M];
int sx, sy, fx, fy, q, sf, s=0;
int dir[M][2] = {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

void add(int sx,int sy,int d,int ct)
{
	int i, j;
	for(i = sx, j = sy; !v[i][j]; i += dir[d][0], j += dir[d][1])
		if(!min[d][i][j])
		{
			min[d][i][j] = ct;
			car[++sf] = (((i << 9) + j) << 3) + d;
			if((i == fx) && (j == fy)) s = ct;
		} 
}

int main ()
{
	int i, j, d, n, m;
	freopen("car.in","r",stdin);
	freopen("car.out","w",stdout);
	scanf("%d %d", &n, &m);
	scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
	
	for(i = 0; i <= n + 1; i++)
		for(j = 0; j <= m + 1; j++)	v[i][j]=1;

	for(i = 1; i <= n; i++)
		for(j = 1;j <= m; j++) scanf("%d", &v[i][j]);

	for(sf = -1, i = 0; i < M; i++)	add(sx, sy, i, 1);

	for(q = 0; (q <= sf) && (!s); q++)
	{
		i = car[q] >> 12;
		j = (car[q] & Y) >> 3;
		d = car[q] & D;
		add(i, j, (d + 1) % M, min[d][i][j] + 1);
		add(i, j, (d + M - 1) % M, min[d][i][j] + 1);
	}
	s--;
	printf("%d\n",s);
	return 0;
}