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)