Cod sursa(job #2676459)

Utilizator cristi_macoveiMacovei Cristian cristi_macovei Data 24 noiembrie 2020 13:13:57
Problema Car Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#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;
  }