Pagini recente » Cod sursa (job #2100656) | Cod sursa (job #3222877) | Cod sursa (job #1610208) | Cod sursa (job #1286485) | Cod sursa (job #2271878)
#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 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 (int _dir, int _x, int _y, int _dist): dir(_dir), x(_x), y(_y), dist(_dist) {};
bool operator < (const var &other) const {
return ((this -> dist) < other.dist);
}
};
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);
}
}
priority_queue < var > Set;
for (int d = 0; d < 8; ++d) {
dist[d][bx][by] = 0;
Set.push({d, bx, by, 0});
}
while(!Set.empty()) {
auto tmp = Set.top();
int dir = tmp.dir;
int x = tmp.x;
int y = tmp.y;
int len = tmp.dist;
Set.pop();
if(dist[dir][x][y] != len) continue;
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;
Set.push({way, nx, ny, cost});
}
}
}
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;
}