Cod sursa(job #1657427)

Utilizator pickleVictor Andrei pickle Data 20 martie 2016 14:45:59
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string.h>
#include <string>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<pii, int> ppiii;
ifstream fin ("car.in");
ofstream fout ("car.out");

const int INF = 0x3f3f3f3f;
const int Nmax = 555;

int N, M, si, sj, fi, fj, ni, nj, ndir, lvl = 0;
int d[Nmax][Nmax][8];
char vis[Nmax][Nmax][8];
char bd[Nmax][Nmax];
queue<ppiii> Q[2];

int di[8]={-1,-1,0,1,1,1,0,-1};
int dj[8]={0,1,1,1,0,-1,-1,-1};

inline int min(int x, int y) { return x < y ? x : y;}
inline int max(int x, int y) { return x > y ? x : y;}
inline int abs(int x) { return x > 0 ? x : -x; }

void pp() {
  cout << string(80, '=') << endl;
  for(int i = 0; i < N; ++i)
  for(int j = 0; j < M; ++j) {
    cout << '('<< i << "x" << j << "):[";
      cout << d[i][j][0];
    for (int dir = 1; dir < 8; ++dir)
      cout << ',' << d[i][j][dir];
    cout << ']';
    cout << (j ==  M-1 ? '\n' :  '#');
  }
}

int main() {
  fin >> N >> M;
  fin >> si >> sj >> fi >> fj;
  --si, --sj, --fi, --fj;

  memset(d, -1, sizeof(d));
  for(int i = 0; i < N; ++i)
  for(int j = 0; j < M; ++j) {
    fin >> bd[i][j];
  }

  for(int dir = 0; dir < 8; ++dir) {
    d[si][sj][dir] = 0;
    Q[lvl].push({{si, sj}, dir});
  }

  bool done = 0;
  while(!done) {
    while(!Q[lvl].empty()) {
      ppiii P = Q[lvl].front(); Q[lvl].pop();
      pii pos = P.first;
      int dir = P.second;
      vis[pos.first][pos.second][dir] = 1;
      if (pos.first == fi && pos.second == fj) {
        done = 1;
        break;
      }
      // don't change direction
      ni = pos.first + di[dir];
      nj = pos.second + dj[dir];
      while(ni >= 0 && ni < N && nj >= 0 && nj < M && bd[ni][nj] == '0' && vis[ni][nj][dir] == 0) {
        if (d[ni][nj][dir] == -1 || d[ni][nj][dir] > d[pos.first][pos.second][dir]) {
          d[ni][nj][dir] = d[pos.first][pos.second][dir];
          Q[lvl].push({{ni, nj}, dir});
        }
        ni += di[dir];
        nj += dj[dir];
      }
      // change direction
      for(int i = -1; i < 2; i += 2) {
        ndir = (dir+i+8)&7;
        ni = pos.first;
        nj = pos.second;
        if (vis[ni][nj][ndir])
          continue;
        if (d[ni][nj][ndir] == -1 || d[ni][nj][ndir] > d[pos.first][pos.second][dir] + 1) {
          d[ni][nj][ndir] = d[pos.first][pos.second][dir] + 1;
          Q[1-lvl].push({{ni, nj}, ndir});
        }
      }
    }
    lvl = 1-lvl;
    if (Q[lvl].empty())
      done = 1;
  }
  //pp();
  int ans = INF;
  for(int dir = 0; dir < 8; ++dir) {
    if (d[fi][fj][dir] == -1)
      continue;
    ans = min(ans, d[fi][fj][dir]);
  }
  fout << (ans == INF ? -1 : ans) << endl;

  return 0;
}