Pagini recente » Cod sursa (job #1149638) | Cod sursa (job #601818) | Cod sursa (job #2796964) | Cod sursa (job #1326152) | Cod sursa (job #2439456)
#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[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 j = 0; j < n; ++j) {
for (int k = 0; k < m; ++k) {
dist[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[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.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];
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[nx][ny]) {
int np = (pos + turnDist);
if (np >= 4) np -= 4;
dist[nx][ny] = newCost;
DQ[np][top[np]++] = {newDir, nx, ny, newCost};
}
}
}
top[pos] = 0;
}
}
if (dist[ex][ey] == INT_MAX) {
cout << -1;
} else {
cout << dist[ex][ey];
}
return 0;
}