Cod sursa(job #1171484)

Utilizator RengelBotocan Bogdan Rengel Data 15 aprilie 2014 19:56:13
Problema Car Scor 80
Compilator cpp Status done
Runda ubb_acm_etapa_individuala1 Marime 1.25 kb

#include <cstdio>

#define nMax 505
#define dirs 8

int A[nMax][nMax], min[dirs][nMax][nMax], car[nMax*nMax*dirs];
int xi, yi, xf, yf, q, sf, s = 0;
int dir[dirs][2] =
{
	{ 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 },
	{ -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }
};
int n, m;

void Add(int xi, int yi, int d, int ct){
	int i, j;
	for (i = xi, j = yi; !A[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 == xf) && (j == yf))
			s = ct;
	}
}

void Read()
{
	scanf("%d%d", &n, &m);
	scanf("%d%d%d%d", &xi, &yi, &xf, &yf);

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

}

int main(){

	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	
	Read();

	int i, j, d, n, m;

	for (sf = -1, i = 0; i < dirs; ++i)
		Add(xi, yi, i, 1);
	
	for (q = 0; (q <= sf) && (!s); ++q){
		i = car[q] >> 12;
		j = (car[q] & 4090) >> 3;
		d = car[q] & 7;
		Add(i, j, (d + 1) % dirs, min[d][i][j] + 1);
		Add(i, j, (d + dirs - 1) % dirs, min[d][i][j] + 1);
	}
	s--;
	printf("%d\n", s);
	fclose(stdin);
	fclose(stdout);
	return 0;
}