Pagini recente » Cod sursa (job #2006515) | Cod sursa (job #2365407) | Cod sursa (job #2605205) | Cod sursa (job #1906323) | Cod sursa (job #2439453)
#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];
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 pos = 0, cnt = 0; cnt < 4; pos = (pos + 1) % 4) {
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 = 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]) {
int np = (pos + turnDist) % 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;
}