Pagini recente » Cod sursa (job #2457969) | Cod sursa (job #3194099) | Cod sursa (job #1595824) | Cod sursa (job #3221308) | Cod sursa (job #2676459)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
const int NMAX = 5e2;
const int INF = 1e9 + 7;
// N, NE, E, SE, S, SW, W, NW
const int d8i[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int d8j[] = { 0, 1, 1, 1, 0, -1, -1, -1};
class QElem {
public:
int i, j;
int dir;
int cost;
QElem() = default;
QElem(int i, int j, int dir, int cost):
i(i), j(j), dir(dir), cost(cost) {};
bool operator < (const QElem& other) const {
return this->cost < other.cost;
}
bool operator > (const QElem& other) const {
return this->cost > other.cost;
}
};
int n, m;
int start_i, start_j;
int end_i, end_j;
bool a[1 + NMAX + 1][1 + NMAX + 1];
int c[1 + NMAX + 1][1 + NMAX + 1][8];
std::priority_queue<QElem, std::vector<QElem>, std::greater<>> pq;
void read() {
std::ifstream in("car.in");
in >> n >> m;
in >> start_i >> start_j;
in >> end_i >> end_j;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
in >> a[i][j];
for (int dir = 0; dir < 8; ++dir)
c[i][j][dir] = INF;
}
}
in.close();
}
void dijkstra() {
for (int dir = 0; dir < 8; ++dir) {
pq.emplace(start_i, start_j, dir, 0);
c[start_i][start_j][dir] = 0;
}
while (!pq.empty()) {
QElem node = pq.top();
pq.pop();
if (node.cost > c[node.i][node.j][node.dir])
continue;
for (int dir = -1; dir <= 1; ++dir) {
QElem next(node.i + d8i[node.dir] * !dir, node.j + d8j[node.dir] * !dir, (8 + node.dir + dir) % 8, node.cost + (dir != 0));
if (!a[next.i][next.j] && c[next.i][next.j][next.dir] > next.cost) {
c[next.i][next.j][next.dir] = next.cost;
pq.push(next);
}
}
}
}
int main() {
read();
dijkstra();
int ans = c[end_i][end_j][0];
for (int dir = 1; dir < 8; ++dir)
ans = std::min(ans, c[end_i][end_j][dir]);
std::ofstream out("car.out");
out << (ans == INF ? -1 : ans) << '\n';
out.close();
return 0;
}