Cod sursa(job #2439782)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 16 iulie 2019 21:09:03
Problema Car Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 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], trans[8][8];
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 i = 0; i < 8; ++i) {
		for (int j = 0; j <= 4; ++j) {
			int le = (8 + i - j) % 8;
			int ri = (8 + i + j) % 8;
			trans[i][le] = j;
			trans[i][ri] = j;
		}
	}
 
	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 = trans[newDir][it.dir];

					dist[newDir][it.x][it.y] = min(dist[newDir][it.x][it.y], it.cost + turnDist);
					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;
}