Cod sursa(job #1688611)

Utilizator lflorin29Florin Laiu lflorin29 Data 13 aprilie 2016 17:05:05
Problema Car Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <bits/stdc++.h>

using namespace std;

const int dx[] = {-1, -1, -1, 1, 1, 1, 0, 0};
const int dy[] = {0, 1, -1, 0, 1, -1, 1, -1};

struct stare
{
  int i , j , dir;
  stare(int i = 0, int j = 0, int dir = 0) : i(i), j(j), dir(dir) {};
  stare operator + (int D) const
  {
    return stare(i + dx[D], j + dy[D], D);
  }
};

const int MAXN = 507;

/*/
0  1   2   3  4   5   6  7
N, NE, NV, S, SE, SV, E, V
/*/

int N, M, A[MAXN][MAXN], X1, Y1,x2, y2;
vector <int> li[10];
int d[MAXN][MAXN][10];
bool va[MAXN][MAXN][10];

void citire()
{
  ifstream in("car.in");
  in >> N >> M>>X1>>Y1>>x2>>y2;
  for(int i = 1; i <= N; ++i)
    for(int j = 1; j <= M; ++j)
       in >> A[i][j];
}

void init()
{
  li[0] = {1, 2};
  li[1] = {0, 6};
  li[2] = {0, 7};
  li[3] = {4, 5};
  li[4] = {3, 6};
  li[5] = {3, 7};
  li[6] = {1, 4};
  li[7] = {2, 5};
}

bool este(int i , int j)
{
  return i>=1&&j>=1&&i<=N&&j<=M&&A[i][j]==0;
}

void mk(stare it, queue<stare>&q)
{
  va[it.i][it.j][it.dir] = 0;

  stare same (it.i + dx[it.dir], it.j + dy[it.dir], it.dir);
  if(este(same.i, same.j) && d[it.i][it.j][it.dir] < d[same.i][same.j][same.dir])
  {
    d[same.i][same.j][same.dir] = d[it.i][it.j][it.dir];
    if(!va[same.i][same.j][same.dir])
      va[same.i][same.j][same.dir] = 1, q.push(same);
  }

  int tmpd = d[it.i][it.j][it.dir];

  for(auto e : li[it.dir])
  {
    stare goTo(it.i, it.j, e);
    if(!este(goTo.i, goTo.j)) continue;
    int &actd = d[goTo.i][goTo.j][e];
    if(tmpd + 1 < actd)
    {
      actd = tmpd+1;
      if(!va[goTo.i][goTo.j][e])
        va[goTo.i][goTo.j][e] = 1, q.push(goTo);
    }
  }
}

void solve()
{
  for(int i = 1;i<=N; ++i)
    for(int j=1;j<=M;++j)
      for(int k=0; k<8; ++k)
        d[i][j][k] = 1 << 22;
  queue < stare>q;
  stare act(X1, Y1);
  for(int k = 0; k < 8; ++k)
  {
    q.push(stare (act.i, act.j, k));
    va[act.i][act.j][k]=1;
    d[act.i][act.j][k] = 0;
  }

  while(!q.empty())
  {
    auto it = q.front();
    q.pop();
    mk(it, q);
  }

  int ans=1<<22;
  for(int k=0;k<8;++k)ans=min(ans,d[x2][y2][k]);
  if(ans==(1<<22)) ans = -1;
  ofstream("car.out")<<ans;
}
int main()
{
  citire();
  init();
  solve();
}