Cod sursa(job #2595151)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 7 aprilie 2020 11:37:23
Problema Car Scor 50
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <bits/stdc++.h>

using namespace std;

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

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

const int INF = 1e9;
const int DIM = 502;

int harta[DIM][DIM];
int cost[DIM][DIM][8];

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

bool vis[DIM][DIM][8];

main()
{
	int n, m;
	fin >> n >> m;
	
	int x1, y1, x2, y2;
	fin >> x1 >> y1 >> x2 >> y2;
	
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			fin >> harta[i][j];
			
			for(int dir = 0; dir < 8; ++dir)
				cost[i][j][dir] = INF;
		}
	
	for(int i = 0; i <= n + 1; ++i)
		harta[i][0] = harta[i][m + 1] = 1;
	
	for(int j = 0; j <= m + 1; ++j)
		harta[0][j] = harta[n + 1][j] = 1;
		
	queue <tuple <int, int, int> > q;
	
	for(int dir = 0; dir < 8; ++dir)
	{
		cost[x1][y1][dir] = 0;
		q.push({x1, y1, dir});
		vis[x1][y1][dir] = true;
	}
	
	while(!q.empty())
	{
		int x, y, dir;
		tie(x, y, dir) = q.front();
		q.pop();
		
		vis[x][y][dir] = false;
		
		for(int i = 0; i <= 4; ++i)
		{
			int ndir = ((dir + i) & 7);
			int nx = x + dx[ndir];
			int ny = y + dy[ndir];
			
			if(harta[nx][ny] == 0 && cost[nx][ny][ndir] > cost[x][y][dir] + i)
			{
				cost[nx][ny][ndir] = cost[x][y][dir] + i;
				
				if(vis[nx][ny][ndir] == false)
				{
					vis[nx][ny][ndir] = true;
					q.push({nx, ny, ndir});
				}
			}
			
			ndir = ((dir - i + 8) & 7);
			nx = x + dx[ndir];
			ny = y + dy[ndir];
			
			if(harta[nx][ny] == 0 && cost[nx][ny][ndir] > cost[x][y][dir] + i)
			{
				cost[nx][ny][ndir] = cost[x][y][dir] + i;
				
				if(vis[nx][ny][ndir] == false)
				{
					vis[nx][ny][ndir] = true;
					q.push({nx, ny, ndir});
				}
			}
		}
	}
	
	int ans = INF;
	
	for(int dir = 0; dir < 8; ++dir)
		ans = min(ans, cost[x2][y2][dir]);
	
	if(ans == INF)
		ans = -1;
	
	fout << ans << '\n';
}