Problem:

 

全探索お姉さんの休日

全探索お姉さんはとても優秀な女性である。
お姉さんは格子状の道の経路の数え上げを数千程度なら簡単に数え上げてしまう。

あなたと全探索お姉さんは今、六角形のタイルが敷き詰められた部屋にいる。
お姉さんは初めて見る六角形にとても興奮している様子である。
六角形の並びを座標に表すことに不慣れなお姉さんは図1のような座標系で部屋を表した。

図1

あなたはこの座標系上である地点からある地点まで移動したい。
しかし、お姉さんは 1 分ごとに動きたい方向をあなたに指示する。
いつものお姉さんなら同じ座標の場所を通らないようにあなたに移動の指示を出すだろう。
しかし、この座標系に不慣れなお姉さんは|x&times;y&times;t|(x：x 座標、y：y座標、t:最初の指示からの経過時間[分])を 6 で割った余り
に対応する方向（図で示す番号と対応）を指示するだけで、まったくのでたらめな方向にあなたを誘導する。

図2

お姉さんを傷つけたくないあなたは、お姉さんの指示をできるだけ守りつつ目的地までたどり着きたい。
あなたは許された行動は下の 7 つの行動である。

方向 0 へ 1 タイル移動

方向 1 へ 1 タイル移動

方向 2 へ 1 タイル移動

方向 3 へ 1 タイル移動

方向 4 へ 1 タイル移動

方向 5 へ 1 タイル移動

その場に留まる

お姉さんが指示を出した直後にあなたはこれら行動のうちの必ず1つを行う。

部屋には家具があり家具が配置されているタイルの中に移動することはできない。
また、y 座標の絶対値が ly を超えたり x 座標の絶対値が lx を超えるような移動は許されていない。
しかし、お姉さんはそのような移動を指示することがある。
指示を無視するとはお姉さんが示した方向と異なる方向へ移動するか、
もしくは、その場に留まることである。

目的地にたどり着くために最小で何度指示を無視すれば良いかを出力せよ。
目的地にたどり着くことが不可能な場合は -1 を出力せよ。

Input

入力は以下の形式で与えられる。

sx sy gx gy
n
x1 y1
...
xi yi
...
xn yn
lx ly

ここで、

sx, sy は出発地点の座標

gx, gy は目的地の座標

n は部屋に配置されている家具の数

xi, yi は家具があるタイルの座標

lx, ly は移動できる X, Y それぞれの座標の絶対値の上限
である。

Constraints

入力はすべて整数

 -lx ≤ sx, gx ≤ lx

 -ly ≤ sy, gy ≤ ly

 (sx, sy) &ne; (gx, gy)

 (xi, yi) &ne; (sx, sy)(1≤i≤n)

 (xi, yi) &ne; (gx, gy)(1≤i≤n)

 (xi, yi) &ne; (xj, yj)(i &ne; j)

 0≤ n ≤ 1000

 -lx ≤ xi ≤ lx (1≤i≤n)

 -ly ≤ yi ≤ ly (1≤i≤n)

 0 < lx, ly ≤ 100

Output

出力は1つの整数を含む1行で出力せよ。
目的地にたどり着ける場合は、最小の指示を無視する回数を出力せよ。
目的地にたどり着くことが不可能な場合は-1を出力せよ。

Sample Input 1

0 0 0 2
0
2 2

Output for the Sample Input 1

0

Sample Input 2

0 0 0 2
6
0 1
1 0
1 -1
0 -1
-1 -1
-1 0
2 2

Output for the Sample Input 2

-1

Sample Input 3

0 0 0 2
1
0 1
2 2

Output for the Sample Input 3

1



Sample input:
0 0 0 2
0
2 2


Sample output:
0

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop

sx, sy, gx, gy = map(int, input().split())
n = int(input())
outs = {tuple(map(int, input().split())) for _ in range(n)}
lx, ly = map(int, input().split())
for x in range(-lx - 1, lx + 2):
  outs.add((x, -ly - 1))
  outs.add((x, ly + 1))
for y in range(-ly - 1, ly + 2):
  outs.add((-lx - 1, y))
  outs.add((lx + 1, y))

dic = {}
dic[(0, sx, sy)] = 0
que = []
heappush(que, (0, 0, sx, sy))
vec1 = ((0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0))
vec2 = ((0, 1), (1, 1), (1, 0), (1, -1), (-1, 0), (-1, 1))
while que:
  score, time, x, y = heappop(que)
  if (x, y) == (gx, gy):
    print(score)
    break
  vec = vec2 if x % 2 else vec1
  inst = vec[abs(x * y * time) % 6]
  new_time = (time + 1) % 6
  for dx, dy in vec:
    nx, ny = x + dx, y + dy
    if (nx, ny) in outs: continue
    new_score = score if (dx, dy) == inst else score + 1
    if (new_time, nx, ny) not in dic or dic[(new_time, nx, ny)] > new_score:
      dic[(new_time, nx, ny)] = new_score
      heappush(que, (new_score, new_time, nx, ny))
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
dd = [(0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (0, 0)]
sx, sy, gx, gy = map(int, raw_input().split())
n = input()
P = {tuple(map(int, raw_input().split())) for i in xrange(n)}
lx, ly = map(int, raw_input().split())

INF = 10**18

dist = {(0, sx, sy): 0}
que = [(0, 0, sx, sy)]
while que:
    co, t, x, y = heappop(que)
    if dist.get((t, x, y), INF) < co:
        continue
    ox, oy = dd[(x*y*t) % 6]
    for dx, dy in dd:
        if dx == ox and dy == oy:
            continue
        nx = x+dx; ny = y+dy
        if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
            continue
        if co+1 < dist.get(((t+1)%6, nx, ny), INF):
            dist[(t+1)%6, nx, ny] = co+1
            heappush(que, (co+1, (t+1)%6, nx, ny))
    nx = x+ox; ny = y+oy
    if (nx, ny) not in P and abs(nx)<=lx and abs(ny)<=ly:
        x += ox; y += oy
        for dx, dy in dd:
            nx = x+dx; ny = y+dy
            if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
                continue
            if co < dist.get(((t+1)%6, nx, ny), INF):
                dist[(t+1)%6, nx, ny] = co
                heappush(que, (co, (t+1)%6, nx, ny))
v = min(dist.get((t, gx, gy), INF) for t in xrange(6))
print -1 if v == INF else v

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
dd = [(0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (0, 0)]
sx, sy, gx, gy = map(int, raw_input().split())
n = input()
P = {tuple(map(int, raw_input().split())) for i in xrange(n)}
lx, ly = map(int, raw_input().split())

INF = 10**18

dist = {(1, sx, sy): 0}
que = [(0, 1, sx, sy)]
while que:
    co, t, x, y = heappop(que)
    print co, t, x, y
    if dist.get((t, x, y), INF) < co:
        continue
    ox, oy = dd[(x*y*t) % 6]
    for dx, dy in dd:
        if dx == ox and dy == oy:
            continue
        nx = x+dx; ny = y+dy
        if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
            continue
        if co+1 < dist.get(((t+1)%6, nx, ny), INF):
            dist[(t+1)%6, nx, ny] = co+1
            heappush(que, (co+1, (t+1)%6, nx, ny))
    nx = x+ox; ny = y+oy
    if (nx, ny) not in P and abs(nx)<=lx and abs(ny)<=ly:
        x += ox; y += oy
        for dx, dy in dd:
            nx = x+dx; ny = y+dy
            if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
                continue
            if co < dist.get(((t+1)%6, nx, ny), INF):
                dist[(t+1)%6, nx, ny] = co
                heappush(que, (co, (t+1)%6, nx, ny))
v = min(dist.get((t, gx, gy), INF) for t in xrange(6))
print -1 if v == INF else v

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
dd = [(0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (0, 0)]
sx, sy, gx, gy = map(int, raw_input().split())
n = input()
P = {tuple(map(int, raw_input().split())) for i in xrange(n)}
lx, ly = map(int, raw_input().split())

INF = 10**18

dist = {(1, sx, sy): 0}
que = [(0, 1, sx, sy)]
while que:
    co, t, x, y = heappop(que)
    if dist.get((t, x, y), INF) < co:
        continue
    ox, oy = dd[(x*y*t) % 6]
    for dx, dy in dd:
        if dx == ox and dy == oy:
            continue
        nx = x+dx; ny = y+dy
        if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
            continue
        if co+1 < dist.get(((t+1)%6, nx, ny), INF):
            dist[(t+1)%6, nx, ny] = co+1
            heappush(que, (co+1, (t+1)%6, nx, ny))
    nx = x+ox; ny = y+oy
    if (nx, ny) not in P and abs(nx)<=lx and abs(ny)<=ly:
        x += ox; y += oy
        for dx, dy in dd:
            nx = x+dx; ny = y+dy
            if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
                continue
            if co < dist.get(((t+1)%6, nx, ny), INF):
                dist[(t+1)%6, nx, ny] = co
                heappush(que, (co, (t+1)%6, nx, ny))
v = min(dist.get((t, gx, gy), INF) for t in xrange(6))
print -1 if v == INF else v

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

sx, sy, gx, gy = map(int, input().split())
n = int(input())
outs = {tuple(map(int, input().split())) for _ in range(n)}
lx, ly = map(int, input().split())
for x in range(-lx - 1, lx + 2):
  outs.add((x, -ly - 1))
  outs.add((x, ly + 1))
for y in range(-ly - 1, ly + 2):
  outs.add((-lx - 1, y))
  outs.add((lx + 1, y))

dic = {}
dic[(0, sx, sy)] = 0
que = []
heappush(que, (0, 0, sx, sy))
vec1 = ((0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0))
vec2 = ((0, 1), (1, 1), (1, 0), (0, -1), (-1, 0), (-1, 1))
while que:
  score, time, x, y = heappop(que)
  if (x, y) == (gx, gy):
    print(score)
    break
  vec = vec2 if x % 2 else vec1
  inst = vec[abs(x * y * time) % 6]
  new_time = (time + 1) % 6
  for dx, dy in vec:
    nx, ny = x + dx, y + dy
    if (nx, ny) in outs: continue
    new_score = score if (dx, dy) == inst else score + 1
    if (new_time, nx, ny) not in dic or dic[(new_time, nx, ny)] > new_score:
      dic[(new_time, nx, ny)] = new_score
      heappush(que, (new_score, new_time, nx, ny))

  if (new_time, x, y) not in dic or dic[(new_time, x, y)] > score + 1:
    dic[(new_time, x, y)] = score + 1
    heappush(que, (score + 1, new_time, x, y))
else:
  print(-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
dd = [
    [(0, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (0, 0)],
    [(0, 1), (1, 1), (1,  0), (0, -1), (-1,  0), (-1, 1), (0, 0)]
]
sx, sy, gx, gy = map(int, raw_input().split())
n = input()
P = {tuple(map(int, raw_input().split())) for i in xrange(n)}
lx, ly = map(int, raw_input().split())

INF = 10**18

dist = {(0, sx, sy): 0}
que = [(0, 0, sx, sy)]
while que:
    co, t, x, y = heappop(que)
    if dist.get((t, x, y), INF) < co:
        continue
    ox, oy = dd[x%2][abs(x*y*t) % 6]
    if (x+ox, y+oy) not in P and abs(x+ox) <= lx and abs(y+oy) <= ly:
        if co < dist.get(((t+1)%6, x+ox, y+oy), INF):
            dist[(t+1)%6, x+ox, y+oy] = co
            heappush(que, (co, (t+1)%6, x+ox, y+oy))
    for dx, dy in dd[x%2]:
        if dx == ox and dy == oy:
            continue
        nx = x+dx; ny = y+dy
        if (nx, ny) in P or abs(nx)>lx or abs(ny)>ly:
            continue
        if co+1 < dist.get(((t+1)%6, nx, ny), INF):
            dist[(t+1)%6, nx, ny] = co+1
            heappush(que, (co+1, (t+1)%6, nx, ny))
v = min(dist.get((t, gx, gy), INF) for t in xrange(6))
print -1 if v == INF else v

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10000000)
input=lambda : sys.stdin.readline().rstrip()

sx,sy,gx,gy=map(int,input().split())
n=int(input())
que=deque()
field=[[[0 for k in range(6)] for j in range(201)]for i in range(201)]

for i in range(n):
    x,y=map(int,input().split())
    for j in range(6):
        field[y+100][x+100][j]+=1
lx,ly=map(int,input().split())

field[sy+100][sx+100][0]=0
que.append((sy+100,sx+100,0,0))
r = [[(1,0),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1)],[(1,0),(1,1),(0,1),(-1,0),(0,-1),(1,-1)]]
while que:
    y,x,t,c=que.popleft()
    if field[y][x][t%6]:
        continue
    else:
        field[y][x][t%6]=1
    if (y,x)==(gy+100,gx+100):
        print(c)
        break
    for i in range(6):
        if abs(y-100+r[x%2][i][0])<=ly and abs(x-100+r[x%2][i][1])<=lx and not field[y+r[x%2][i][0]][x+r[x%2][i][1]][(t+1)%6]:
            if i==abs((y-100)*(x-100)*(t))%6:
                que.appendleft((y+r[x%2][i][0],x+r[x%2][i][1],t+1,c))
            else:
                que.append((y+r[x%2][i][0],x+r[x%2][i][1],t+1,c+1))
    if not field[y][x][(t+1)%6]:
        que.append((y,x,t+1,c+1))
else:
    print(-1)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    dd0 = [(0,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(0,0)]
    dd1 = [(0,1),(1,1),(1,0),(0,-1),(-1,0),(-1,1),(0,0)]
    dd = [dd0, dd1]

    def f(n):
        sx,sy,gx,gy = LI()
        n = I()
        fs = set([tuple(LI()) for _ in range(n)])
        lx,ly = LI()

        def search(s, g):
            d = collections.defaultdict(lambda: inf)
            s = tuple(list(s) + [0])
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                if (u[0],u[1]) == g:
                    return k
                v[u] = True
                ddi = 0 if u[0] % 2 == 0 else 1
                di,dj = dd[ddi][abs(u[0]*u[1]*u[2])%6]
                nu = (u[2] + 1) % 6
                uv = (u[0]+di, u[1]+dj, nu)
                if d[uv] > k and abs(uv[0]) <= lx and abs(uv[1]) <= ly and not ((uv[0],uv[1]) in fs):
                    d[uv] = k
                    heapq.heappush(q, (k, uv))

                vd = k + 1
                for di,dj in dd[ddi]:
                    uv = (u[0]+di, u[1]+dj, nu)
                    if v[uv] or abs(uv[0]) > lx or abs(uv[1]) > ly or (uv[0],uv[1]) in fs:
                        continue
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return None
        r = search((sx,sy),(gx,gy))
        if r is None:
            return -1
        return r

    while 1:
        n = 1
        if n == 0:
            break
        rr.append(f(n))
        break
        # print('rr', rr[-1])

    return '\n'.join(map(str,rr))


print(main())