Pagini recente » Istoria paginii utilizator/cozazura | Cod sursa (job #2032176) | Cod sursa (job #1264258) | Cod sursa (job #1962143) | Cod sursa (job #2676464)
#include <iostream>
#include <fstream>
#include <vector>
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];
int list_index = 0;
std::vector<QElem> list[2];
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) {
list[list_index].emplace_back(start_i, start_j, dir, 0);
c[start_i][start_j][dir] = 0;
}
while (!list[0].empty() || !list[1].empty()) {
if (list[list_index].empty())
list_index = 1 - list_index;
QElem node = list[list_index].back();
list[list_index].pop_back();
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;
if (next.cost == node.cost)
list[list_index].push_back(next);
else
list[1 - list_index].push_back(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;
}