Cod sursa(job #1043094)

Utilizator AnonymouslegionAnonymous Anonymouslegion Data 27 noiembrie 2013 23:40:30
Problema Car Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

class node{
public:
  int x, y, d, t;

  node(){};

  node(int T){
    t = T;
    d = T % 8;
    y = T / 8 % 501;
    x = T / 8 / 501;
  }

  node(int x1, int y1, int d1){
    x = x1;
    y = y1;
    d = d1;
    t = x * 8 * 501 + y * 8 + d;
  }
};

node down(node p){
  return node(p.x, p.y, (p.d + 7) % 8);
}

node up(node p){
  return node(p.x, p.y, (p.d + 1) % 8);
}

node next(node p){
  return node(p.x + dx[p.d], p.y + dy[p.d], p.d);
}

int startx, starty, destx, desty;
int n, m, dist[2008008], mat[505][505];

inline int valid(node &x){
  if(x.x > n || x.x < 1 || x.y > m || x.y < 1 || dist[x.t] != -1)
    return 0;
  if(mat[x.x][x.y] == 1)
    return 0;
  return 1;
}

int main(){
  ifstream in("car.in");
  ofstream out("car.out");

  memset(dist, -1, sizeof(dist));

  in >> n >> m;
  in >> startx >> starty >> destx >> desty;

  for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j)
      in >> mat[i][j];

  vector<node> q1, q2;

  for(int i = 0; i < 8; ++i){
    node t(startx, starty, i);
    q2.push_back(t);
    dist[t.t] = 0;
  }

  while(!q2.empty()){
    q1 = q2;
    q2.clear();
    for(int i = 0; i < q1.size(); ++i){
      node nxt = next(q1[i]);
      if(valid(nxt)){
        dist[nxt.t] = dist[q1[i].t];
        q1.push_back(nxt);
      }
    }
    for(int i = 0; i < q1.size(); ++i){
      node n1 = up(q1[i]), n2 = down(q1[i]);
      if(valid(n1)){
        dist[n1.t] = dist[q1[i].t] + 1;
        q2.push_back(n1);
      }
      if(valid(n2)){
        dist[n2.t] = dist[q1[i].t] + 1;
        q2.push_back(n2);
      }
    }
  }

  int ans = 2e9;
  for(int i = 0; i < 8; ++i){
    node t(destx, desty, i);
    ans = min(ans, dist[t.t]);
  }

  out << ans;

  return 0;
}