Pagini recente » Cod sursa (job #1354092) | Cod sursa (job #591258) | Cod sursa (job #3241879) | Cod sursa (job #2031719) | Cod sursa (job #2439848)
#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 trans[8][8];
int dist[8][NMax][NMax];
var DQ[3][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) {
if (road[j][k]) continue;
for (int i = 0; i < 8; ++i) {
dist[i][j][k] = INT_MAX;
}
}
}
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 == 3) pos = 0;
if (top[pos] == 0) {
++cnt;
} else {
cnt = 1;
for (int i = 0; i < top[pos]; ++i) {
var 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 >= 3) 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 >= 3) np -= 3;
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;
}