Cod sursa(job #2096556)

Utilizator GoogalAbabei Daniel Googal Data 29 decembrie 2017 13:49:50
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 500;
const int VMAX = 1 + (1 << 21);
const int INF = 1 << 20;
const int DCD = 511;

class Coord {
  public:
    int x;
    int y;
};

int dist[1 + VMAX];
int n, m, res;
int a[1 + NMAX][1 + NMAX];
vector < int > l[2];

short int dx[] = {1, 1, 0, -1, -1, -1,  0,  1};
short int dy[] = {0, 1, 1,  1,  0, -1, -1, -1};
Coord st, fn;

int code(int i, int j, int dir) {
  int code = (i << 9) + j + (dir << 18);
  return code;
}

void decode(int state, int &i, int &j, int &dir) {
  j = state & DCD;
  dir = state >> 18;
  i = (state >> 9) & DCD;
}

bool ok(int x, int y) {
  if(x < 1 || y < 1 || x > n || y > m || a[x][y] == 1)
    return false;
  else
    return true;
}

bool expand(int state) {
  int x, y, dir;
  int cstate;

  decode(state, x, y, dir);

  cstate = code(x, y, (dir + 7) % 8);
  if(dist[state] + 1 < dist[cstate]) {
    dist[cstate] = dist[state] + 1;
    l[dist[cstate] & 1].push_back(cstate);
  }

  cstate = code(x, y, (dir + 1) % 8);
  if(dist[state] + 1 < dist[cstate]) {
    dist[cstate] = dist[state] + 1;
    l[dist[cstate] & 1].push_back(cstate);
  }

  x += dx[dir];if(dist[state] + 1 < dist[cstate]) {
    dist[cstate] = dist[state] + 1;
    l[dist[cstate] & 1].push_back(cstate);
  }
  y += dy[dir];

  if(ok(x, y) == false) {
    return false;
  } else {
    cstate = code(x, y, dir);
    if(dist[state] < dist[cstate]) {
      dist[cstate] = dist[state];
      l[dist[cstate] & 1].push_back(cstate);
    }

    if(x == fn.x && y == fn.y)
      return true;
    else
      return false;
  }
}

int main()
{
  in >> n >> m >> st.x >> st.y >> fn.x >> fn.y;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
      in >> a[i][j];
    }
  }

  for(int i = 0; i <= VMAX; i++)
    dist[i] = INF;

  for(int dir = 0; dir < 8; dir++) {
    int state = code(st.x, st.y, dir);
    l[0].push_back(state);
    dist[state] = 0;
  }

  while(0 < l[0].size() + l[1].size()) {
    while(l[res & 1]. size() != 0) {
      int state = l[res & 1][l[res & 1].size() - 1];
      l[res & 1].pop_back();

      if(expand(state) == true) {
        out << res << '\n';
        exit(EXIT_SUCCESS);
      }
    }
    res++;
  }

  out << "-1\n";
  return 0;
}