Cod sursa(job #34536)

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

using namespace std;

#define MN (512)

int C[MN][MN][8];
int m[MN][MN];

const int 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}
};

const int mover[8] = {0, -1, -1, -1, 0, 1, 1, 1},
    movec[8] = {1, 1, 0, -1, -1, -1, 0, 1};

int N, M, startr, startc, endr, endc, X;

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

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

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

queue<Cfg> q;

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

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

	memset(C, -1, sizeof(C));
	//printf("%d\n", C[0][0][0]);
	//return 0;
	int newr, newc;
	for(i = 0; i < 8; ++i) if(inside(newr = startr+mover[i], newc = startc+movec[i]) && !m[newr][newc]) {
		C[newr][newc][i] = 0;
		q.push(make_cfg(newr, newc, i));
		//printf(".\n");
	}
	//return 0;

	for(; !q.empty(); q.pop()) {
		int r = q.front().r, c = q.front().c, d = q.front().d;
		//printf("Trying %d %d %d\n", r, c, d);
		for(i = 0; i < 8; ++i) if(inside(newr = r+mover[i], newc = c+movec[i]) && C[newr][newc][i] == -1 && !m[newr][newc]) {
			C[newr][newc][i] = C[r][c][d]+cost[d][i];
			//printf("Added %d %d %d with cost %d\n", newr, newc, i, C[newr][newc][i]);
			q.push(make_cfg(newr, newc, i));
		}
	}

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

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

	return 0;
}