Pagini recente » Cod sursa (job #2881896) | Cod sursa (job #425116) | Cod sursa (job #1319034) | Cod sursa (job #2881558) | Cod sursa (job #2439452)
#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};
int road[NMax][NMax];
int dist[8][NMax][NMax];
struct var {
int dir, x, y, cost;
};
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;
}
vector < var > DQ[4];
for (int i = 0; i < 8; ++i) {
dist[i][bx][by] = 0;
DQ[0].push_back({i, bx, by, 0});
}
for (int pos = 0, cnt = 0; cnt < 4; pos = (pos + 1) % 4) {
if (DQ[pos].empty()) {
++cnt;
} else {
cnt = 1;
for (int i = 0; i < (int)DQ[pos].size(); ++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]) {
dist[newDir][nx][ny] = newCost;
DQ[(pos + turnDist) % 4].push_back({newDir, nx, ny, newCost});
}
}
}
DQ[pos] = {};
}
}
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;
}