Cod sursa(job #2439452)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 16 iulie 2019 01:34:24
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 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};

int road[NMax][NMax];
int dist[8][NMax][NMax];

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

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;
	}

	vector < var > DQ[4];
	for (int i = 0; i < 8; ++i) {
		dist[i][bx][by] = 0;
		DQ[0].push_back({i, bx, by, 0});
	}

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

			for (int i = 0; i < (int)DQ[pos].size(); ++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]) {
						dist[newDir][nx][ny] = newCost;
						DQ[(pos + turnDist) % 4].push_back({newDir, nx, ny, newCost});
					}
				}
			}

			DQ[pos] = {};
		}
	}
	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;
}