Cod sursa(job #1698943)

Utilizator krityxAdrian Buzea krityx Data 5 mai 2016 18:07:31
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#include <deque>
#define NMAX 501
using namespace std;

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

inline 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 };
	bool A[NMAX][NMAX];
	int N, M, Si, Sj, Di, Dj, C[NMAX][NMAX][8], i, j;
	deque<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_back(position(Si, Sj, i));
	}

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

		int starti = current.direction < 2 ? current.direction + 6 : current.direction - 2;

		for (int k = 0; k < 5; k++)
		{
			i = (starti + k) & 7;
			if (A[current.x + di[i]][current.y + dj[i]] == 0)
			{
				int diff = abs(2 - k);
				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;
					q.push_back(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;
}