Cod sursa(job #1585419)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 30 ianuarie 2016 23:45:41
Problema Car Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <fstream>
#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;
} q[3][kMaxN * kMaxN];
int qs[3];

void SetDist(int x, int y, int d, int cost) {
  int qi = cost % 3;
  q[qi][qs[qi]].x = x;
  q[qi][qs[qi]].y = y;
  q[qi][qs[qi]].d = d;
  ++qs[qi];
  dist[x][y][d] = cost;
}

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)
    SetDist(sx, sy, i, 0);

  for (int cost = 0; qs[0] + qs[1] + qs[2]; ++cost) {
    int crt = cost % 3;
    for (int i = 0; i < qs[crt]; ++i) {
      int x = q[crt][i].x;
      int y = q[crt][i].y;
      int d = q[crt][i].d;
      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])
          SetDist(nx, ny, nd, ncost);
      }
    }
    qs[crt] = 0;
  }

  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;
}