Cod sursa(job #3216624)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 18 martie 2024 19:41:06
Problema Car Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("car.in");
#define cin in
ofstream out("car.out");
#define cout out

const int nmax = 505;
const int dmax = 8;

const int infty = 1e9;
int dist[nmax][nmax][dmax];
int mat[nmax][nmax];

/*
567
4x0
321
*/

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

struct Stare {
	int x, y, d;

	bool operator<(const Stare &other) const {
		if(x != other.x) return x < other.x;
		if(y != other.y) return y < other.y;
		return d < other.d;
	}
};

struct PQSlow {
	priority_queue<pair<int, Stare>> pq;

	void add(Stare s, int d) {
		pq.push({-d, s}); // punem cu - fiindca priority_queue e max-heap
	}

	Stare pop() {
		Stare s = pq.top().second;
		pq.pop();
		return s;
	}

	bool empty() {
		return pq.empty();
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for(int i = 0; i < nmax; i++) {
		for(int j = 0; j < nmax; j++) {
			for(int k = 0; k < dmax; k++) {
				dist[i][j][k] = infty;
			}
		}
	}

	int n, m; cin >> n >> m;
	int sx, sy, fx, fy; cin >> sx >> sy >> fx >> fy;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> mat[i][j];
		}
	}

	PQSlow pq;

	for(int d = 0; d < dmax; d++) {
		dist[sx][sy][d] = 0;
		pq.add({sx, sy, d}, 0);
	}

	while(!pq.empty()) {
		auto stare = pq.pop();
		int x = stare.x;
		int y = stare.y;
		int dir = stare.d;
		int cnt_dist = dist[x][y][dir];

		// Prima oara, incercam sa ne rotim!
		for(int new_dir = 0; new_dir < dmax; new_dir++) {
			if(new_dir == dir) continue;
			int dif = abs(dir - new_dir);
			int new_dist = cnt_dist + min(dif, 8 - dif); 
			if(new_dist < dist[x][y][new_dir]) {
				dist[x][y][new_dir] = new_dist;
				pq.add({x, y, new_dir}, new_dist);
			}
		}

		// A doua oara, incercam sa ne ducem in directia in care ne uitam!
		int nx = x + dx[dir];
		int ny = y + dy[dir];
		if(nx <= 0 || nx > n || ny <= 0 || ny > m) continue; // Iesim din matrice
		if(mat[nx][ny] == 1) continue; // Nu avem voie pe aceasta pozitie (are 1)

		int new_dist = cnt_dist + 0;
		if(new_dist < dist[nx][ny][dir]) {
			dist[nx][ny][dir] = new_dist;
			pq.add({nx, ny, dir}, new_dist);
		}
	}

	int minim = infty;
	for(int d = 0; d < dmax; d++) {
		minim = min(minim, dist[fx][fy][d]);
	}

	if(minim == infty) minim = -1;
	cout << minim << '\n';
}