Cod sursa(job #286828)

Utilizator Omega91Nicodei Eduard Omega91 Data 24 martie 2009 11:06:10
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <cstdio>

const int MASK_used = 1, MASK_added = 2;
const int NMAX = 500;

struct coord {
	int i, j;
} pqArray[NMAX];

struct el {
	char used, dir;
	int dist;
} map[NMAX][NMAX];

int pqSz, N, M;

coord dir[] = { {0, -1}, {-1, -1}, {-1, 0}, {-1, 1},
                 {0, 1}, {1, 1}, {1, 0}, {1, -1} };
coord start, dest;

/* because we're lazy, we're going to implement the pq as a simple list
 * with complexity O(n) for poping and O(1) for pushing */
void pq_push(coord);
coord pq_pop();
void check_neigh(coord);
void citire();
void init();
char calc_ddir(char, char);

int main()
{
	coord c;
	bool good = false;
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);
	citire();
	init();
	while(pqSz) {
		c = pq_pop();
		if (c.i == dest.i && c.j == dest.j) {
			good = true;
			break;
		}
		check_neigh(c);
	}
	if (good) printf("%d\n", map[dest.i][dest.j].dist);
	else printf("-1\n");
}

void citire()
{
	int i, j, aux;
	scanf("%d %d", &N, &M);
	scanf("%d %d %d %d", &start.i, &start.j, &dest.i, &dest.j);
	for (i = 1; i <= N; ++i)
		for (j = 1; j <= M; ++j) {
			scanf("%d ", &aux);
			if (aux) map[i][j].used |= MASK_used;
		}
}

void init()
{
	int i, j, d;
	coord ncrd;
	++N; ++M;
	for (i = 0; i <= N; ++i) map[i][0].used = map[i][M].used = MASK_used;
	for (j = 0; j <= M; ++j) map[0][j].used = map[N][j].used = MASK_used;
	
	for (d = 0; d != 8; ++d) {
		ncrd.i = start.i + dir[d].i;
		ncrd.j = start.j + dir[d].j;
		if ( !(map[ncrd.i][ncrd.j].used & MASK_used) ) {
			map[ncrd.i][ncrd.j].dist = 0;
			map[ncrd.i][ncrd.j].dir = d;
			pq_push(ncrd);
		}
	}
	map[start.i][start.j].used = MASK_used;
		
}

void pq_push(coord x)
{
	pqArray[pqSz++] = x;
}

coord pq_pop()
{
	static int min, minpos, k, c;
	static coord crd, mincrd;
	mincrd = pqArray[0];
	min = map[mincrd.i][mincrd.j].dist;
	minpos = 0;
	for (k = 1; k != pqSz; ++k) {
		crd = pqArray[k];
		c = map[crd.i][crd.j].dist;
		if (min > c) {
			c = min;
			minpos = k;
			mincrd = crd;
		}
	}
	pqArray[minpos] = pqArray[--pqSz];
	return mincrd;
}

void check_neigh(coord crd)
{
	el &c = map[crd.i][crd.j], *n;
	char stdir = c.dir - 2 & 7, endir = (c.dir + 2 & 7) + 1;
	int d;
	coord ncrd;
	for (d = stdir; d != endir; ++d) {
		d = d & 7;
		ncrd.i = crd.i + dir[d].i;
		ncrd.j = crd.j + dir[d].j;
		n = &map[ncrd.i][ncrd.j];
		if (!(n -> used & MASK_used)) {
			if (n -> used & MASK_added) {
				if (n -> dist < c.dist + calc_ddir(c.dir, d)) continue;
			}
			else {
				pq_push(ncrd);
				map[ncrd.i][ncrd.j].used |= MASK_added;
			}
			n -> dist = c.dist + calc_ddir(c.dir, d);
			n -> dir = d;
		}
	}
	c.used |= MASK_used;
}

char abs(signed char x) {
	if (x < 0) return -x;
	return x;
}

inline char calc_ddir(char a, char b)
{
	char x = abs(a - b);
	if (x > 2) return 8 - x;
	return x;
}