Cod sursa(job #2921392)

Utilizator livliviLivia Magureanu livlivi Data 30 august 2022 17:28:37
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <fstream>
#include <vector>
#include <tuple>
#include <deque>

using namespace std;

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

const int kDir = 8;
const int kMax = 2e6;

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

vector<vector<vector<int>>> bfs(int n, int m, vector<vector<bool>>& harta, int xs, int ys) {
	vector<vector<vector<int>>> dist(
		kDir, vector<vector<int>>(
			n + 1, vector<int>(
				m + 1, kMax)));

	deque<tuple<int, int, int>> heap;
	for (int i = 0; i < kDir; i++) {
		dist[i][xs][ys] = 0;
		heap.push_back(make_tuple(xs, ys, i));
	}

	while (!heap.empty()) {
		int dir, x, y;
		tie(x, y, dir) = heap.front();
		int cost = dist[dir][x][y];
		heap.pop_front();

		// merge inainte pe aceeasi directie
		int new_x = x + dx[dir];
		int new_y = y + dy[dir];
		if (harta[new_x][new_y] && dist[dir][new_x][new_y] > cost) {
			dist[dir][new_x][new_y] = cost;
			heap.push_front(make_tuple(new_x, new_y, dir));
		}

		// schimba directia cu 45 de grade
		for (int i = -1; i <= 1; i += 2) {
			int new_dir = (dir + i + kDir) % kDir;
			if (dist[new_dir][x][y] > cost + 1) {
				dist[new_dir][x][y] = cost + 1;
				heap.push_back(make_tuple(x, y, new_dir));
			}
		}
	}

	return dist;
}

int main() {
	int n, m; cin >> n >> m;
	int xs, ys; cin >> xs >> ys;
	int xd, yd; cin >> xd >> yd;

	// true = se poate trece
	vector<vector<bool>> harta(n + 2, vector<bool>(m + 2, false));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x; cin >> x;
			harta[i][j] = (x == 0);
		}
	}

	vector<vector<vector<int>>> dist = bfs(n, m, harta, xs, ys);

	int ans = kMax;
	for (int i = 0; i < kDir; i++) {
		ans = min(ans, dist[i][xd][yd]);
	}

	cout << (ans == kMax ? -1 : ans) << "\n";
	return 0;
}