Cod sursa(job #1491081)

Utilizator vladrochianVlad Rochian vladrochian Data 24 septembrie 2015 19:20:47
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 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 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[5];

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

int main() {
  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 % 5;
    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) {
        int nx = x + dx[nd];
        int ny = y + dy[nd];
        int ncost = cost + min((d - nd) & 7, (nd - d) & 7);
        if (a[nx][ny] && ncost < dist[nx][ny][nd]) {
          dist[nx][ny][nd] = ncost;
          q[ncost % 5].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;
}