Cod sursa(job #1653567)

Utilizator krityxAdrian Buzea krityx Data 16 martie 2016 10:43:56
Problema Car Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <fstream>
#include <queue>
#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;
	}
};

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, i, j; //, A[NMAX][NMAX], C[NMAX][NMAX][8], i, j;
	vector<vector<int>> A;
	vector<vector<vector<int>>> C;
	queue<position> q;
	ifstream f("car.in");
	f >> N >> M >> Si >> Sj >> Di >> Dj;
	A.resize(N + 1);
	A[0].resize(M + 1);
	C.resize(N + 1);
	C[0].resize(M + 1);
	for (i = 1; i <= N; i++)
	{
		A[i].resize(M + 1);
		C[i].resize(M + 1);
		for (j = 1; j <= M; j++)
		{
			C[i][j].resize(8);
			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++)
		{
			int c = current.direction > 4 ? current.direction % 4 : current.direction + 4;
			if (abs(i - c) < 2)
			{
				continue;
			}
			if (current.x + di[i] < 1 || current.y + dj[i] < 1 || current.x + di[i] > N || current.y + dj[i] > M || A[current.x + di[i]][current.y+dj[i]] == 1)
			{
				continue;
			}
			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])
			{
				if (C[current.x + di[i]][current.y + dj[i]][i] == INF)
					q.push(position(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;
			}
		}
	}

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