Cod sursa(job #2439868)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 17 iulie 2019 00:19:39
Problema Car Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.89 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];
bool road[NMax][NMax];
int adj[8][3];
int dist[8][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];
		}
	}
 
	if (road[bx][by] == 1 || road[ex][ey] == 1) {
		cout << -1;
		return 0;
	}

	for (int j = 0; j < n; ++j) {
		for (int k = 0; k < m; ++k) {
			for (int i = 0; i < 8; ++i) {
				dist[i][j][k] = INT_MAX;
			}
		}
	}
 
	deque < var > DQ;
	for (int i = 0; i < 8; ++i) {
		dist[i][bx][by] = 0;
		DQ.push_back({i, bx, by, 0});
	}
 
	for (int i = 0; i < 8; ++i) {
		for (int j = 0; j < 3; ++j) {
			adj[i][j] = (7 + i + j) % 8;
		}
	}
 
	while (!DQ.empty()) {
		var it = DQ.front();
		DQ.pop_front();

		if (it.cost > dist[it.dir][it.x][it.y]) continue;

		for (int i = 0; i < 3; ++i) {
			int nx = it.x + dx[adj[it.dir][i]];
			int ny = it.y + dy[adj[it.dir][i]];
			int turnCost = (i != 1);
			int cost = turnCost + it.cost;

			if (cost < dist[adj[it.dir][i]][it.x][it.y]) {
				dist[adj[it.dir][i]][it.x][it.y] = cost;
				DQ.push_back({adj[it.dir][i], it.x, it.y, cost});
			}

			if (nx < 0 || ny < 0 || nx >= n || ny >= m || road[nx][ny]) continue;

			if (cost < dist[adj[it.dir][i]][nx][ny]) {
				dist[adj[it.dir][i]][nx][ny] = cost;

				if (turnCost == 0) {
					DQ.push_front({adj[it.dir][i], nx, ny, cost});
				} else {
					DQ.push_back({adj[it.dir][i], nx, ny, cost});
				}
			}
		}
	}
	
	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;
}