AOJ 1156: Twirling Robot

自力で解けたけど、北と南を勘違いしていてしばらく考え込んでしまった。

問題はこちら。

問題

ロボットが東を向いてスタート地点にいる。ロボットは今いるマスに書いてある方向に向きをかえて移動していく。ただし、移動させたい方向に対応したコストを払えば、ロボットを任意の向きに１マス動かすことができる。ロボットをスタートからゴールまで移動させるときに必要な最小のコストを答える。

解法

BFSで座標、向き、コストを持ちながら、コスト表を更新していけばいい。コスト表は[向き][座標] = (最小コスト) とすればOK。毎回dxyを作ることで、簡潔に移動コストの計算ができる。つい最近やった、yukicoderの門松問題(3)での経験が生きた。

inf = 10**9
 
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    S = [map(int,raw_input().split()) for i in xrange(H)]
    c = map(int,raw_input().split())
 
    costs = [[[[inf]*W for i in xrange(H)] for j in xrange(3)] for k in xrange(3)]
    costs[2][0][0][0] = 0
    que = [[0,0,1,0,0]]
    while que:
        w,h,dw,dh,cost = que.pop(0)
        if (w,h) == (W-1,H-1): continue
        if costs[dw+1][dh+1][h][w] < cost: continue
 
        dxy = [(dw,dh),(-dh,dw),(-dw,-dh),(dh,-dw)]
 
        for i in xrange(4):
            dx,dy = dxy[i]
            nw,nh = w+dx,h+dy
            if 0 <= nw < W and 0 <= nh < H:
                ncost = cost+bool(i != S[h][w])*c[i]
                if costs[dx+1][dy+1][nh][nw] <= ncost: continue
                costs[dx+1][dy+1][nh][nw] = ncost
                que.append([nw,nh,dx,dy,ncost])
    print min(min(costs[i][j][H-1][W-1] for i in xrange(3)) for j in xrange(3))