Cod sursa(job #2595144)

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

using namespace std;

ifstream 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];

void bfs(int x, int y)
{
	queue <tuple <int, int, int> > q;
	
	for(int dir = 0; dir < 8; ++dir)
	{
		cost[x][y][dir] = 0;
		q.push({x, y, dir});
		vis[x][y][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) % 8;
			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) % 8;
			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});
				}
			}
		}
	}
}

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;
		
	bfs(x1, y1);
	
	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';
}