Google Code Jam Japan 2011 決勝 E. 無限庭園 (Small)

無限庭園

0,0から10,10に行くために、1000,1000を経由するような大きな遠回りが無いと仮定して、迷路を実際に作って、最短路探索。一旦、通路の中央を通る経路で最短路を求め、同じ向きに2回曲がっているごとに、最短距離から2を引く。最短経路が2種類あったら上手くいかないけど、そんなことは無いらしい。

# coding: utf-8

W = 100
H = 100

Dir = [(1,0),(0,1),(-1,0),(0,-1)]       # (dy,dx)

def makemap():
    mode = 0
    tape = ["X"]
    cur = 0
    dir = 0
    cx = cy = 1
    
    global M
    M = [["."]*W for i in range(H)]
    M[1][1] = "*"
    
    for i in range(1000000):
        if cur==len(tape)-1:
            if mode==0:
                if tape[0]=="X":
                    tape[0] = "L"
                elif tape[0]=="L":
                    tape[0] = "X"
                tape = tape*2
                c = cur+1
                tl = len(tape)
                while c<tl:
                    if   tape[c]=="L":  tape[c]="R"
                    elif tape[c]=="R":  tape[c]="L"
                    c += 1
                mode = 1
            else:
                tape += tape[::-1]
                mode = 0
        for j in range(2):
            cy += Dir[dir][0]
            cx += Dir[dir][1]
            if 0<=cy<H and 0<=cx<W:
                M[cy][cx] = "*"
        cur += 1
        if tape[cur]=="L": dir = (dir+3)%4
        if tape[cur]=="R": dir = (dir+1)%4

makemap()

def solve_small(Px,Py,Qx,Qy):
    D = [[-1]*W for i in range(H)]  # 最短距離
    P = [[-1]*W for i in range(H)]  # 移動方向
    D[Py][Px] = 0
    
    for d in xrange(W*H*10):
        if D[Qy][Qx]!=-1:
            break
        for y in range(0,H,2):
         for x in range(0,W,2):
            if D[y][x]==d:
                for j in range(4):
                    dy,dx = Dir[j]
                    ty = y+dy*2
                    tx = x+dx*2
                    if ( 0<=tx<W and 0<=ty<H and
                         M[y+dy][x+dx]=="." and D[ty][tx]==-1 ):
                        D[ty][tx] = d+1
                        P[ty][tx] = j
    # 移動経路
    R = [(Qy,Qx)]
    while R[0] != (Py,Px):
        py = R[0][0]
        px = R[0][1]
        d = P[py][px]
        R = [(py-Dir[d][0]*2,px-Dir[d][1]*2)]+R
    # 差分
    RD = [((R[i+1][0]-R[i][0])/2,(R[i+1][1]-R[i][1])/2) for i in range(len(R)-1)]
    # 曲がった向き
    RD2 = []
    for i in range(len(RD)-1):
        if RD[i]!=RD[i+1]:
            RD2 += [(Dir.index(RD[i])-Dir.index(RD[i+1])+4)%4]
    # 同じ向きに2回曲がっていたら、距離を2短縮できる
    ans = D[Qy][Qx]*2
    for i in range(len(RD2)-1):
        if RD2[i]==RD2[i+1]:
            ans -= 2
    
    return ans

for t in xrange(input()):
    Px,Py,Qx,Qy = map(int,raw_input().split())
    ans = solve_small(Px,Py,Qx,Qy)
    print "Case #%s: %s" % (t+1,ans)