Cod sursa(job #34655)

Utilizator IgnitionMihai Moraru Ignition Data 21 martie 2007 09:44:38
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <stdio.h>
#include <limits.h>
#include <string.h>
#include <queue>

using namespace std;

#define MN (512)

const int move_cost[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}
},
	mover[8] = {0, -1, -1, -1, 0, 1, 1, 1},
	movec[8] = {1, 1, 0, -1, -1, -1, 0, 1};

struct Cfg {
	int r, c, d;
};

int C[MN][MN][8], m[MN][MN];
int N, M, startr, startc, endr, endc, X;
queue<Cfg> q;

inline int inside(int r, int c)
{
	return 0 <= r && r < N && 0 <= c && c < M;
}

inline Cfg make_cfg(int r, int c, int d)
{
	Cfg tmp;
	tmp.r = r; tmp.c = c; tmp.d = d;
	return tmp;
}

int main()
{
	freopen("car.in", "r", stdin);
	freopen("car.out", "w", stdout);

	int i, j, r, c, nr, nc;

	scanf("%d %d %d %d %d %d", &N, &M, &startr, &startc, &endr, &endc);
	--startr; --startc; --endr; --endc;
	for(r = 0; r < N; ++r) for(c = 0; c < M; ++c)
		scanf("%d", &m[r][c]);

	for(r = 0; r < N; ++r) for(c = 0; c < M; ++c) for(i = 0; i < 8; ++i)
		C[r][c][i] = LONG_MAX;
	for(i = 0; i < 8; ++i) if(inside(nr = startr+mover[i], nc = startc+movec[i]) && !m[nr][nc]) {
		C[nr][nc][i] = 0;
		q.push(make_cfg(nr, nc, i));
	}

	for(; !q.empty(); q.pop()) {
		r = q.front().r; c = q.front().c; j = q.front().d;
		for(i = 0; i < 8; ++i) if(inside(nr = r+mover[i], nc = c+movec[i]) &&
				!m[nr][nc] && C[r][c][j]+move_cost[j][i] < C[nr][nc][i]) {
			C[nr][nc][i] = C[r][c][j]+move_cost[j][i];
			q.push(make_cfg(nr, nc, i));
		}
	}

	for(X = LONG_MAX, i = 0; i < 8; ++i) if(C[endr][endc][i] < X)
		X = C[endr][endc][i];
	if(X == LONG_MAX)
		X = -1;

	printf("%d\n", X);

	return 0;
}