Cod sursa(job #2590482)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 28 martie 2020 01:49:17
Problema Car Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#pragma warning(disable:4996)
#define x first.first
#define y first.second
#define z second
using namespace std;

const int NMAX = 502;
const int oo = 0x3f3f3f3f;
bitset <NMAX> viz[NMAX];
bitset <NMAX> a[NMAX];

int dx[8][8] = { { 1, 1, 0, -1, -1, -1, 0, 1 },
				 { 1, 0, -1, -1, -1, 0, 1, 1 },
				 { 0, -1, -1, -1, 0, 1, 1, 1 },
				 { -1, -1, -1, 0, 1, 1, 1, 0 },
				 { -1, -1, 0, 1, 1, 1, 0, -1 },
				 { -1, 0, 1, 1, 1, 0, -1, -1 },
				 { 0, 1, 1, 1, 0, -1, -1, -1 },
				 { 1, 1, 1, 0, -1, -1, -1, 0 } };
int dy[8][8] = { { 0, 1, 1, 1, 0, -1, -1, -1 },
				 { 1, 1, 1, 0, -1, -1, -1, 0 },
				 { 1, 1, 0, -1, -1, -1, 0, 1 },
				 { 1, 0, -1, -1, -1, 0, 1, 1 },
				 { 0, -1, -1, -1, 0, 1, 1, 1 },
				 { -1, -1, -1, 0, 1, 1, 1, 0 },
				 { -1, -1, 0, 1, 1, 1, 0, -1 },
				 { -1, 0, 1, 1, 1, 0, -1, -1 }, };

inline int ind(int i)
{
	if (i > 4) return 8 - i;
	return i;
}

int cost[NMAX][NMAX];

typedef pair <int, int> p;
typedef pair <p, int> pp;

struct cmp
{
	bool operator()(pp a, pp b)
	{
		return cost[a.x][a.y] > cost[b.x][b.y];
	}
};

priority_queue<pp, vector <pp>, cmp> q;


class InParser
{
private:
	FILE* fin;
	char* buff;
	int sp;
	char read()
	{
		++sp;
		if (sp == 4096)
		{
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}
public:
	InParser(const char* nume)
	{
		sp = 4095;
		fin = fopen(nume, "r");
		buff = new char[4096];
	}
	InParser& operator >> (int& n)
	{
		char c;
		while (!isdigit(c = read()));
		n = c - '0';
		while (isdigit(c = read()))
			n = n * 10 + c - '0';
		return *this;
	}
};

InParser fin("car.in");
ofstream fout("car.out");

int n, m, t, sx, sy, fx, fy;

inline bool ok(int i, int j)
{
	return i && j && i <= n && j <= n && a[i][j] == 0 && viz[i][j] == 0;
}

void solve()
{
	pp c;
	while (!q.empty())
	{
		do
		{
			c = q.top();
			q.pop();
		} while (!q.empty() && viz[c.x][c.y] == 1);
		viz[c.x][c.y] = 1;
		for (int i = 0; i < 8; ++i)
		{
			int nx = c.x + dx[c.z][i];
			int ny = c.y + dy[c.z][i];
			int val = cost[c.x][c.y] + ind(i);
			if (ok(nx, ny) && val < cost[nx][ny])
			{
				cost[nx][ny] = val;
				q.push({ { nx, ny }, (i + c.z) % 8 });
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	fin >> sx >> sy >> fx >> fy;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
		{
			fin >> t;
			a[i][j] = t;
			cost[i][j] = oo;
		}

	if (a[sx][sy] == 1 || a[fx][fy] == 1)
	{
		fout << "-1\n";
		return 0;
	}

	cost[sx][sy] = 0;

	for (int i = 0; i < 8; ++i)
	{
		int nx = sx + dx[0][i];
		int ny = sy + dy[0][i];
		if (ok(nx, ny))
		{
			cost[nx][ny] = 0;
			q.push({ { nx, ny }, i });
		}
	}

	viz[sx][sy] = 1;

	solve();

	if (viz[fx][fy] == 0)
		fout << "-1\n";

	else fout << cost[fx][fy] << "\n";

	return 0;
}