Cod sursa(job #903392)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 martie 2013 20:25:27
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 15000000

int m, n, dir[505][505][8];
bool a[505][505];

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

struct coord {
	int x, y, d;
} S, F;
queue <coord> Q[2];

coord init (int x, int y, int d)
{
	coord a;
	a.x = x, a.y = y, a.d = d;
	return a;
}

bool Check ()
{
	for (int i = 0; i < 2; ++i)
		if ((Q[i].front().x == F.x && Q[i].front().y == F.y))
			return false;
	if (Q[0].empty() && Q[1].empty())
		return false;
	return true;
}

void Way (coord C)
{
	Q[0].push (C);
	while (Check())
	{
		int u;
		for (u = 0; Q[u].empty(); ++u);
		int i = Q[u].front().x;
		int j = Q[u].front().y;
		int d = Q[u].front().d;
		int Min = d + 7, Max = d + 9;
		if (d == -1)
			Min = 0, Max = 7;
		for (int K = Min; K <= Max; ++K)
		{
			int k = K % 8;
			int ii = i + dx[k];
			int jj = j + dy[k];
			int c = (d == k || d == -1) ? 0 : 1;
			if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj] && dir[i][j][d] + c < dir[ii][jj][k])
			{
				dir[ii][jj][k] = dir[i][j][d] + c;
				Q[c].push (init (ii, jj, k));
			}
		}
		Q[u].pop();			
	}
}	

int main ()
{
	ifstream fin ("car.in");
	fin >> m >> n >> S.x >> S.y >> F.x >> F.y;
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < n; ++j)
		{
			fin >> a[i][j];
			for (int k = 0; k < 8; ++k)
				dir[i][j][k] = INF;
		}
	S.x--, S.y--, F.x--, F.y--;
	for (int k = 0; k < 8; ++k)
		dir[S.x][S.y][k] = 0;
	fin.close();
	ofstream fout ("car.out");
	S.d = -1;
	Way (S);		
	int M = INF;
	for (int i = 0; i < 8; ++i)
		M = min (M, dir[F.x][F.y][i]);
	if (M != INF)
		fout << M;
	else
		fout << "-1";
	fout.close ();
	return 0;
}