Cod sursa(job #902972)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 martie 2013 17:48:01
Problema Car Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <fstream>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;

#define INF 3000

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;
deque <coord> Q;

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

void Way (coord C)
{
	Q.push_back(C);
	while (!(Q.front().x == F.x && Q.front().y == F.y) && !Q.empty())
	{
		int i = Q.front().x;
		int j = Q.front().y;
		int M = INF, d = -1;
		Q.pop_front();
		if (!(i == S.x && j == S.y))
		for (int l = 0; l < 8; ++l)
		{
			if (dir[i][j][l] < M)
			{ 
				M = dir[i][j][l];
				d = l;
			}
		}
		else
			M = 0;
		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 && M + c < dir[ii][jj][k] && !a[ii][jj])
			{
				cout << i << " " << j << "(" << M << ") -> " << ii << " " << jj << " (" << M + c << ")\n";
				dir[ii][jj][k] = M + c;
				if (!c)
					Q.push_front(init (ii,jj));
				else
					Q.push_back(init (ii, jj));
			}
		}
	}
}	

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