Cod sursa(job #1491084)

Utilizator vladrochianVlad Rochian vladrochian Data 24 septembrie 2015 19:28:16
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;

const int kMaxN = 505, kInf = 0x3f3f3f3f;
const int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};

ifstream fin("car.in");
ofstream fout("car.out");

int N, M, sx, sy, fx, fy;
bool a[kMaxN][kMaxN];
int dcost[8][8];
int dist[kMaxN][kMaxN][8];

struct Node {
  int x, y, d;
  Node(int x, int y, int d) : x(x), y(y), d(d) {}
};
queue<Node> q[3];

bool QueuesNotEmpty() {
  for (int i = 0; i < 3; ++i)
    if (!q[i].empty()) return true;
  return false;
}

int main() {
  for (int i = 0; i < 8; ++i)
    for (int j = 0; j < 8; ++j)
      dcost[i][j] = min((i - j) & 7, (j - i) & 7);

  fin >> N >> M >> sx >> sy >> fx >> fy;
  for (int i = 1; i <= N; ++i)
    for (int j = 1; j <= M; ++j) {
      char c;
      fin >> c;
      if (c == '0')
        a[i][j] = true;
    }

  memset(dist, kInf, sizeof dist);
  for (int i = 0; i < 8; ++i) {
    q[0].emplace(sx, sy, i);
    dist[sx][sy][i] = 0;
  }

  for (int cost = 0; QueuesNotEmpty(); ++cost) {
    int crt = cost % 3;
    while (!q[crt].empty()) {
      int x = q[crt].front().x;
      int y = q[crt].front().y;
      int d = q[crt].front().d;
      q[crt].pop();
      if (dist[x][y][d] != cost)
        continue;
      for (int nd = 0; nd < 8; ++nd) {
        if (dcost[d][nd] > 2)
          continue;
        int nx = x + dx[nd];
        int ny = y + dy[nd];
        int ncost = cost + dcost[d][nd];
        if (a[nx][ny] && ncost < dist[nx][ny][nd]) {
          dist[nx][ny][nd] = ncost;
          q[ncost % 3].emplace(nx, ny, nd);
        }
      }
    }
  }

  int ans = kInf;
  for (int i = 0; i < 8; ++i)
    ans = min(ans, dist[fx][fy][i]);
  fout << (ans == kInf ? -1 : ans) << "\n";
  return 0;
}