Cod sursa(job #3148364)

Utilizator moldovan_robert_lolMoldovan Robert moldovan_robert_lol Data 31 august 2023 15:40:54
Problema Car Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>
#include <tuple>
#include <cmath>

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

int x, y;
int is, js, ie, je;
int arr[501][501];
int dist[501][501][8];
int cost[8][8];

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

inline bool in_mat(int i, int j) {
	return !(i<1||i>x||j<1||j>y);
}

void bfs(int is, int js, int init_dir) {
	std::priority_queue<std::tuple<int,int,int,int>> q;
	q.emplace(0,is,js,init_dir);
	dist[is][js][init_dir] = 0;

	int tmp, i, j, d;
	while (!q.empty()) {
		std::tie(tmp,i,j,d) = q.top();
		q.pop();

		for (int k = 0; k < 8; k++) {
			const int inou = i+dx[k];
			const int jnou = j+dy[k];

			int c = cost[d][k];
			if (in_mat(inou,jnou)&&!arr[inou][jnou]&&dist[inou][jnou][k]>dist[i][j][d]+c) {
				dist[inou][jnou][k] = dist[i][j][d]+c;
				q.emplace(dist[i][j][d]+c,inou,jnou,k);
			}
		}
	}
}

int main() {
	for (int i = 0; i < 8; i++) {
		for (int j = 1; j <= 4; j++) {
			cost[i][(i-j+8)&7] = cost[i][(i+j)&7] = j;
		}
	}

	fin >> x >> y;
	fin >> is >> js >> ie >> je;
	for (int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {
			fin >> arr[i][j];
		}
	}

	memset(dist,0x3f,sizeof(dist));
	for (int i = 0; i < 8; i++) {
		bfs(is,js,i);
	}

	int ret = -1;
	for (int i = 0; i < 8; i++) {
		if (ret==-1||ret>dist[ie][je][i]) {
			ret = dist[ie][je][i];
		}
	}

	fout << ret << "\n";
}