Cod sursa(job #2724162)

Utilizator FrostfireMagirescu Tudor Frostfire Data 16 martie 2021 17:16:16
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <iostream>
#include <fstream>
#define NMAX 500
#define f first
#define s second
#define inf 2000000000

using namespace std;

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

int n, m, cost[NMAX+10][NMAX+10][8], dr[10], st[10];
pair <pair <int, int>, int> Q[5][NMAX*NMAX*4+10];
bool v[NMAX+10][NMAX+10], viz[NMAX+10][NMAX+10][8];
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
pair <int, int> p1, p2;

int main()
{
	fin >> n >> m >> p1.f >> p1.s >> p2.f >> p2.s;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			fin >> v[i][j];
	if(v[p1.f][p1.s] || v[p2.f][p2.s])
		{	fout << -1 << '\n';
			return 0;
		}
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			for(int t=0; t<8; t++)
				cost[i][j][t] = inf;
	int curr = 0;
	for(int t=0; t<8; t++)
		{	Q[0][++dr[0]] = {p1, t};
			cost[p1.f][p1.s][t] = 0;
		}
	for(int i=0; i<5; i++)
		st[i] = 1;

	while(st[0] <= dr[0] || st[1] <= dr[1] || st[2] <= dr[2] || st[3] <= dr[3] || st[4] <= dr[4])
		{	while(st[curr] > dr[curr])
				{	curr++;
					if(curr == 5)
						curr = 0;
				}
			pair <pair <int, int>, int > a = Q[curr][st[curr]];
			st[curr]++;
			int r = a.f.f, c = a.f.s, dir = a.s;
			if(viz[r][c][dir])
				continue;
			viz[r][c][dir] = 1;
			if(r == p2.f && c == p2.s)
				{	fout << cost[r][c][dir] << '\n';
					return 0;
				}

			for(int t=1; t<=4; t++)
				{	int newdir = (dir + t) % 8, val = (curr + t) % 5;
					if(t + cost[r][c][dir] < cost[r][c][newdir])
						{	cost[r][c][newdir] = cost[r][c][dir] + t;
							dr[val]++;
							Q[val][dr[val]] = {{r, c}, newdir};
						}
					newdir = (dir - t + 8) % 8;
					if(t + cost[r][c][dir] < cost[r][c][newdir])
						{	cost[r][c][newdir] = cost[r][c][dir] + t;
							dr[val]++;
							Q[val][dr[val]] = {{r, c}, newdir};
						}	 
				}
			pair <int, int> vec = {dx[dir] + r, dy[dir] + c};
			if(vec.f && vec.s && vec.f <= n && vec.s <= m && !v[vec.f][vec.s] && cost[r][c][dir] < cost[vec.f][vec.s][dir])
				{	cost[vec.f][vec.s][dir] = cost[r][c][dir];
					dr[curr]++;
					Q[curr][dr[curr]] = {vec, dir};
				}
		}
	fout << -1 << '\n';
	return 0;
}