Cod sursa(job #2439454)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 16 iulie 2019 01:41:13
Problema Car Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

struct var {
	int dir, x, y, cost;
};

int top[4];
int road[NMax][NMax];
int dist[8][NMax][NMax];
var DQ[4][NMax * NMax];

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

	int n, m;
	cin >> n >> m;

	int bx, by, ex, ey;
	cin >> bx >> by >> ex >> ey;
	--bx; --by; --ex; --ey;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> road[i][j];
		}
	}

	for (int i = 0; i < 8; ++i) {
		for (int j = 0; j < n; ++j) {
			for (int k = 0; k < m; ++k) {
				dist[i][j][k] = INT_MAX;
			}
		}
	}

	if (road[bx][by] == 1 || road[ex][ey] == 1) {
		cout << -1;
		return 0;
	}

	for (int i = 0; i < 8; ++i) {
		dist[i][bx][by] = 0;
		DQ[0][top[0]++] = {i, bx, by, 0};
	}

	for (int pos = 0, cnt = 0; cnt < 4; ++pos) {
		if (pos == 4) pos = 0;
		if (top[pos] == 0) {
			++cnt;
		} else {
			cnt = 1;

			for (int i = 0; i < top[pos]; ++i) {
				auto it = DQ[pos][i];
				if (it.cost > dist[it.dir][it.x][it.y]) continue;

				for (int newDir = 0; newDir < 8; ++newDir) {
					int nx = it.x + dx[newDir];
					int ny = it.y + dy[newDir];
					int turnDist = abs(newDir - it.dir);
					if (turnDist == 4) continue;
					int newCost = it.cost + turnDist;

					if (nx < 0 || ny < 0 || nx >= n || ny >= m || road[nx][ny]) continue;
					if (newCost < dist[newDir][nx][ny]) {
						int np = (pos + turnDist);
						if (np >= 4) np -= 4;
						
						dist[newDir][nx][ny] = newCost;
						DQ[np][top[np]++] = {newDir, nx, ny, newCost};
					}
				}
			}
			top[pos] = 0;
		}
	}
	int mn = INT_MAX;
	for (int i = 0; i < 8; ++i) {
		mn = min(mn, dist[i][ex][ey]);
	}

	if (mn == INT_MAX) {
		cout << -1;
	} else {
		cout << mn;
	}
	return 0;
}