Cod sursa(job #1652966)

Utilizator krityxAdrian Buzea krityx Data 15 martie 2016 17:14:31
Problema Car Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <queue>
#define NMAX 504
using namespace std;

struct position
{
	int x, y, direction;
	position(int a, int b, int c)
	{
		x = a;
		y = b;
		direction = c;
	}
};

int abs(int x)
{
	if (x < 0)
	{
		return -x;
	}
	return x;
}

int main()
{
	const int INF = 1 << 30;
	const int di[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	const int dj[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
	int N, M, Si, Sj, Di, Dj, A[NMAX][NMAX], C[NMAX][NMAX][8], i, j;
	queue<position> q;
	ifstream f("car.in");
	f >> N >> M >> Si >> Sj >> Di >> Dj;
	for (i = 1; i <= N; i++)
	{
		for (j = 1; j <= M; j++)
		{
			f >> A[i][j];
			if (A[i][j] == 0)
			{
				for (int k = 0; k < 8; k++)
				{
					C[i][j][k] = INF;
				}
			}
		}
	}
	f.close();

	for (i = 0; i < 8; i++)
	{
		C[Si][Sj][i] = 0;
		q.push(position(Si, Sj, i));
	}

	while (!q.empty())
	{
		position current = q.front();
		q.pop();

		for (i = 0; i < 8; i++)
		{
			if (A[current.x + di[i]][current.y + dj[i]] == 0)
			{
				int diff = abs(i - current.direction) % 4;
				if (C[current.x][current.y][current.direction] + diff < C[current.x + di[i]][current.y + dj[i]][i])
				{
					C[current.x + di[i]][current.y + dj[i]][i] = C[current.x][current.y][current.direction] + diff;
					if (current.x + di[i] > 0 && current.y + dj[i] > 0 && current.x + di[i] <= N && current.y + dj[i] <= M)
					{
						q.push(position(current.x + di[i], current.y + dj[i], i));
					}
				}
			}
			
		}
	}

	int min = C[Di][Dj][0];

	for (i = 1; i < 8; i++)
	{
		if (C[Di][Dj][i] < min)
		{
			min = C[Di][Dj][i];
		}
	}

	if (min == INF)
	{
		min = -1;
	}

	ofstream g("car.out");
	g << min;
	g.close();
	



	return 0;
}