Cod sursa(job #902621)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 martie 2013 15:31:39
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;

#define INF 3000

int m, n, 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;
deque <coord> Q;

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

void Way (coord C)
{
	Q.push_back (C);
	while (!Q.empty())
	{
		int i = Q.front().x;
		int j = Q.front().y;
		int d = Q.front().d;
		Q.pop_front();
		for (int k = 0; k < 8; ++k)
		{
			int ii = i + dx[k];
			int jj = j + dy[k];
			int c = d == -1 ? 0 : (abs (d - k) < 4 ? abs (d - k) : 8 - abs (d - k));
			if (ii >= 0 && jj >= 0 && ii < m && jj < n && a[i][j] + c < a[ii][jj])
			{
				a[ii][jj] = a[i][j] + c;
				if (!c)
					Q.push_front (init (ii, jj, k));
				else
					Q.push_back (init (ii, jj, k));
			}
		}
	}					
}
	

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)
		{
			int x;
			fin >> x;
			if (x == 1)
				a[i][j] = -1;
			else
				a[i][j] = INF;
		}
	S.x--, S.y--, F.x--, F.y--;
	a[S.x][S.y] = 0;
	fin.close();
	ofstream fout ("car.out");
	S.d = -1;
	Way (S);			
	/*for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
			cout << a[i][j] << " ";
		cout << "\n";
	}*/
	fout << (a[F.x][F.y] != INF ? a[F.x][F.y] : -1);
	fout.close ();
	return 0;
}