Cod sursa(job #86822)

Utilizator victorsbVictor Rusu victorsb Data 25 septembrie 2007 19:07:47
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define Nmax 512
#define Cmax 100000
#define Dmax 8
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define unghi first
#define x second.first
#define y second.second
#define sz(a) (int)((a).size())

const int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, m, x0, y0, x1, y1;
int mat[Nmax][Nmax];
char s[4 * Nmax], *buf;
int d[Nmax][Nmax][Dmax];
vector< pair<int, pair<int, int> > > list[Cmax];

int get()
{
	int ret = 0;

	if (*buf == '1') ret = 1;
	++buf;
	while (*buf == ' ') ++buf;

	return ret;
}

void citire()
{
	int i, j;

	scanf("%d %d", &n, &m);
	scanf("%d %d %d %d\n", &x0, &y0, &x1, &y1);
	for (i = 1; i <= n; ++i)
	{
		fgets(s, Nmax * 4, stdin);
		buf = s;
		for (j = 1; j <= m; ++j)
			mat[i][j] = get();
	}
}

int ok(int a, int b)
{
	if (1 <= a && a <= n)
		if (1 <= b && b <= m)
			return 1;
	return 0;
}

void solve()
{
	int i, j, X, Y, U, sol = INF;

	memset(d, 0x3f, sizeof(d));
    for (i = 0; i < 8; ++i)
	{
		d[x0][y0][i] = 0;
		list[0].pb(mp(i, mp(x0, y0)));
	}

	for (i = 0; i < Cmax; ++i)
	for (j = 0; j < sz(list[i]); ++j)
		if (d[list[i][j].x][list[i][j].y][list[i][j].unghi] == i)
		{
			U = list[i][j].unghi;
			X = list[i][j].x + dx[U];
			Y = list[i][j].y + dy[U];

			if (ok(X,Y) && !mat[X][Y] && d[X][Y][U] > i)
			{
				d[X][Y][U] = i;
				list[i].pb(mp(U, mp(X, Y)));
			}

			X = list[i][j].x;
			Y = list[i][j].y;

			if (U < 7 && d[X][Y][U + 1] > i + 1)
			{
				d[X][Y][U + 1] = i + 1;
				list[i + 1].pb(mp(U + 1, mp(X, Y)));
			}
			else if (d[X][Y][0] > i + 1)
			{
 				d[X][Y][0] = i + 1;
				list[i + 1].pb(mp(0, mp(X, Y)));
			}

			if (U > 0 && d[X][Y][U - 1] > i + 1)
			{
				d[X][Y][U - 1] = i + 1;
				list[i + 1].pb(mp(U - 1, mp(X, Y)));
			}
			else if (d[X][Y][7] > i + 1)
			{
 				d[X][Y][7] = i + 1;
				list[i + 1].pb(mp(7, mp(X, Y)));
			}
		}

	for (i = 0; i < 8; ++i)
		if (d[x1][y1][i] < sol)
			sol = d[x1][y1][i];

	printf("%d\n", sol);
}

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

	citire();
	solve();

	return 0;
}