Cod sursa(job #903049)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 martie 2013 18:15:41
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <queue>
#include <algorithm>
#include <iostream>
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;
} S, F;
queue <coord> Q[5];

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

bool Check ()
{
	for (int i = 0; i < 4; ++i)
		if ((Q[i].front().x == F.x && Q[i].front().y == F.y))
			return false;
	if (Q[0].empty() && Q[1].empty() && Q[2].empty() && Q[3].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 M = INF, d = -1;
		if (i == S.x && j == S.y)
			M = 0;
		else
		for (int l = 0; l < 8; ++l)
			if (dir[i][j][l] < M)
			{
				M = dir[i][j][l];
				d = l;
			}
		for (int k = 0; k < 8; ++k)
		{
			int ii = i + dx[k];
			int jj = j + dy[k];
			int c = d == -1 ? 0 : (abs (k - d) < 4 ? abs (k - d) : 8 - abs (k - d));
			if (ii >= 0 && jj >= 0 && ii < m && jj < n && !a[ii][jj] && M + c < dir[ii][jj][k])
			{
				dir[ii][jj][k] = M + c;
				Q[c].push (init (ii, jj));
			}
		}
		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");
	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;
}