Pagini recente » Cod sursa (job #204007) | Cod sursa (job #584024) | Cod sursa (job #1225898) | Cod sursa (job #1506518) | Cod sursa (job #2271892)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
ifstream fin("car.in");
ofstream fout("car.out");
const int NMax = 1e5;
const int INF = 1e9;
const int dx[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int dy[] = {-1, 0, 1, 1, 1, 0, -1, -1};
vector < vector < int > > road;
vector < vector < int > > dist[8];
struct var {
int dir, x, y, dist;
};
var DQ[NMax];
int main() {
int n, m; fin >> n >> m;
int bx, by, ex, ey;
fin >> bx >> by >> ex >> ey;
--bx; --by; --ex; --ey;
road.resize(n);
for (auto &x: road) x.resize(m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
fin >> road[i][j];
}
}
if (road[bx][by] == 1 || road[ex][ey] == 1) {
fout << "-1";
exit(0);
}
for (auto &y: dist) {
y.resize(n);
for (auto &x: y) {
x.resize(m, INF);
}
}
int lo, hi;
lo = hi = 0;
for (int d = 0; d < 8; ++d) {
dist[d][bx][by] = 0;
DQ[hi++] = {d, bx, by, 0};
}
while(lo <= hi) {
auto tmp = DQ[lo % NMax];
int dir = tmp.dir;
int x = tmp.x;
int y = tmp.y;
int len = tmp.dist;
for (int way = 0; way < 8; ++way) {
int nx = x + dx[way];
int ny = y + dy[way];
if(nx < 0 || ny < 0 || nx >= n || ny >= m || road[nx][ny] == 1) continue;
int cost = len + abs(way - dir);
if (cost < dist[way][nx][ny]) {
dist[way][nx][ny] = cost;
DQ[hi % NMax] = {way, nx, ny, cost};
++hi;
}
}
++lo;
}
int mn = INF;
for (int i = 0; i < 8; ++i) {
mn = min(mn, dist[i][ex][ey]);
}
if(mn == INF) {
fout << "-1";
} else {
fout << mn;
}
return 0;
}