AOJ2425.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int Weight;
const Weight INF = 1000000000;

struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, int weight) {
  g[src].push_back((Edge){src, dest, weight});
}

void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int getId(int x, int y, int turn) { return (x+105) * 210*6 + (y+105) * 6 + turn; }

vector<pair<int,int>> neighbor(int x, int y) {
  vector<pair<int,int>> res;
  res.emplace_back(x, y+1);
  res.emplace_back(x+1, y+(x+INF)%2);
  res.emplace_back(x+1, y-1+(x+INF)%2);
  res.emplace_back(x, y-1);
  res.emplace_back(x-1, y-1+(x+INF)%2);
  res.emplace_back(x-1, y+(x+INF)%2);
  return res;
}

int main() {
  Graph g(210*210*6);
  int sx, sy, gx, gy, n, lx, ly, x, y;
  set<pair<int,int>> p;
  cin >> sx >> sy >> gx >> gy >> n;
  REP(i,n) {
    cin >> x >> y;
    p.insert({x, y});
  }
  cin >> lx >> ly;
  for (x = -104; x < 104; x++)
    for (y = -104; y < 104; y++) {
      if (x < -lx || x > lx || y < -ly || y > ly) continue;
      if (p.find({x, y}) != p.end()) continue;
      vector<pair<int,int>> ne = neighbor(x, y);
      REP (i,6) REP(j,6)
        add_edge(g, getId(x, y, i), getId(ne[j].first, ne[j].second, (i+1)%6),
                 (abs(x) % 6 * abs(y) % 6 * i % 6 != j));
      REP (i,6)
        add_edge(g, getId(x, y, i), getId(x, y, (i+1)%6), 1);
    }
  Array d;
  dijkstra(g, d, getId(sx, sy, 0));
  int res = INF;
  REP(i,6) res = min(res, d[getId(gx, gy, i)]);
  cout << (res == INF ? -1 : res) << endl;
  return 0;
}