Cod sursa(job #2676464)

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