Cod sursa(job #908542)

Utilizator toranagahVlad Badelita toranagah Data 9 martie 2013 17:01:00
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <algorithm>
#include <deque>
#include <fstream>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

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

const int MAX_N = 505;
const int INF = 1 << 30;
const int DIRECTIONS = 8;
const int DX[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int DY[] = {1, 1, 0, -1, -1, -1, 0, 1};

struct Point {
    int x, y;
    Point();
    Point(int, int);
};

int N, M;
int Si, Sj, Fi, Fj;
bool mat[MAX_N][MAX_N];
deque<pair<Point, int> > dq;
int cost[MAX_N][MAX_N][DIRECTIONS];
int answer = INF;

void read_input();
void solve();
void print_output();
inline bool bounded(int x, int y);
inline void check_next(int x, int y, int d, int c, int n);

int main() {
  read_input();
  solve();
  print_output();
  return 0;
}

void read_input() {
  fin >> N >> M;
  fin >> Si >> Sj >> Fi >> Fj;
  
  for (int i = 1; i <= N; ++i) {
      for (int j = 1; j <= M; ++j) {
          fin >> mat[i][j];
          for (int k = 0; k < DIRECTIONS; ++k) {
            cost[i][j][k] = INF;
          }
      }
  }
}

void solve() {
  for (int k = 0; k < DIRECTIONS; ++k) {
    cost[Si][Sj][k] = 0;
    dq.push_back(make_pair(Point(Si, Sj), k));
  }

  while (!dq.empty()) {
    int x = dq.front().first.x;
    int y = dq.front().first.y;
    int dir = dq.front().second;
    int c = cost[x][y][dir];
    dq.pop_front();

    //keep direction
    if (bounded(x + DX[dir], y + DY[dir]) && 
        c < cost[x + DX[dir]][y + DY[dir]][dir]) {
      cost[x + DX[dir]][y + DY[dir]][dir] = c;
      dq.push_front(make_pair(Point(x + DX[dir], y + DY[dir]), dir));
    }

    //change direction
    check_next(x, y, dir, c, 1);
    check_next(x, y, dir, c, -1);
  }

  for (int k = 0; k < DIRECTIONS; ++k) {
    answer = min(answer, cost[Fi][Fj][k]);
  }
  if (answer == INF) answer = -1;
}


void print_output() {
  fout << answer;
}

inline bool bounded(int x, int y) {
  if (x < 1 || x > N) return false;
  if (y < 1 || y > M) return false;
  return (!mat[x][y]);
}

inline void check_next(int x, int y, int d, int c, int n) {
  int next = d + n;
  if (next < 0) next = 7;
  if (next > 7) next = 0;

  if (c + 1 < cost[x][y][next]) {
    if (cost[x][y][next] == INF) {
      dq.push_back(make_pair(Point(x, y), next));
    }
    cost[x][y][next] = c + 1;
  }
}

Point::Point() {
  x = y = 0;
}

Point::Point(int xx, int yy) {
  x = xx;
  y = yy;
}