Pagini recente » Cod sursa (job #2251927) | Cod sursa (job #797635) | Cod sursa (job #1911144) | Cod sursa (job #227) | Cod sursa (job #3238942)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 505, inf = 0x3F3F3F3F;
const int dir = 8;
const int ox[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int oy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
int n, m, xs, ys, xf, yf;
int dist[nmax][nmax][dir];
bitset<nmax> a[nmax], visited[nmax][dir];
queue<tuple<int, int, int>> q[3];
bool inside(int x, int y) {
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void dial(int xs, int ys) {
memset(dist, inf, sizeof(dist));
int current_queue = 0, no_elements = dir;
for (int i = 0; i < dir; ++i) {
q[current_queue].push({xs, ys, i});
dist[xs][ys][i] = 0;
}
while (no_elements > 0) {
while (q[current_queue].empty())
current_queue = (current_queue + 1) % 3;
int x, y, direction;
tie(x, y, direction) = q[current_queue].front();
q[current_queue].pop();
--no_elements;
if (!visited[x][y][direction]) {
for (int k = -2; k <= 2; ++k) {
int newdirection = (direction + k + dir) % dir;
int nx = x + ox[newdirection];
int ny = y + oy[newdirection];
if (inside(nx, ny) && !a[nx][ny] && !visited[nx][ny][newdirection] && dist[nx][ny][newdirection] > dist[x][y][direction] + abs(k)) {
dist[nx][ny][newdirection] = dist[x][y][direction] + abs(k);
q[dist[nx][ny][newdirection] % 3].push({nx, ny, newdirection});
++no_elements;
}
}
visited[x][y][direction] = 1;
}
}
}
int main() {
ifstream cin("car.in");
ofstream cout("car.out");
cin >> n >> m >> xs >> ys >> xf >> yf;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int x;
cin >> x;
a[i][j] = x;
}
dial(xs, ys);
int ans = inf;
for (int i = 0; i < dir; ++i)
ans = min(ans, dist[xf][yf][i]);
if (ans == inf)
cout << -1;
else
cout << ans;
return 0;
}