Problem:


Problem D: Twirling Robot 

Let's play a game using a robot on a rectangular board 
covered with a square mesh (Figure D-1).
The robot is initially set at the start square in the northwest corner
facing the east direction.
The goal of this game is to lead the robot
to the goal square in the southeast corner.

Figure D-1: Example of a board

The robot can execute the following five types of commands.

 "Straight":
 Keep the current direction of the robot, and move forward to the next square.
 "Right":
 Turn right with 90 degrees from the current direction, and move forward to the next square.
 "Back":
 Turn to the reverse direction, and move forward to the next square.
 "Left":
 Turn left with 90 degrees from the current direction, and move forward to the next square.
 "Halt":
 Stop at the current square to finish the game.

Each square has one of these commands assigned as shown in Figure D-2.
The robot executes the command assigned to the square where it resides,
unless the player gives another command to be executed instead.
Each time the player gives an explicit command, 
the player has to pay the cost that depends on the command type.

Figure D-2: Example of commands assigned to squares

The robot can visit the same square several times during a game.
The player loses the game when the robot goes out of the board
or it executes a "Halt" command before arriving at the goal square.

Your task is to write a program that calculates the minimum cost to lead the robot
from the start square to the goal one.

Input

The input is a sequence of datasets. 
The end of the input is indicated by a line containing two zeros separated by a space.
Each dataset is formatted as follows.

w h

s(1,1)  ... s(1,w)

s(2,1)  ... s(2,w)

...

s(h,1)  ... s(h,w)

c0 c1 c2 c3

The integers h and w are the numbers of rows and columns of the board, 
respectively.
You may assume 2 ≤ h ≤ 30 and 2 ≤ w ≤ 30. 
Each of the following h lines consists of w numbers delimited by a space.
The number s(i, j) represents the command assigned to the square 
in the i-th row and the j-th column as follows.

 0: "Straight"
 

 1: "Right"

 2: "Back"

 3: "Left"

 4: "Halt"

You can assume that a "Halt" command is assigned to the goal square.
Note that "Halt" commands may be assigned to other squares, too.

The last line of a dataset contains four integers 
c0, c1, c2, and c3, delimited by a space,  
indicating the costs that the player has to pay 
when the player gives
"Straight", "Right", "Back", and "Left" commands
respectively.
The player cannot give "Halt" commands.
You can assume that all the values of 
c0, c1, c2, and c3
are between 1 and 9, inclusive.

Output

For each dataset, print a line only having a decimal integer indicating the minimum cost 
required to lead the robot to the goal.
No other characters should be on the output line.

Sample Input

8 3
0 0 0 0 0 0 0 1
2 3 0 1 4 0 0 1
3 3 0 0 0 0 0 4
9 9 1 9
4 4
3 3 4 0
1 2 4 4
1 1 1 0
0 2 4 4
8 7 2 1
2 8
2 2
4 1
0 4
1 3
1 0
2 1
0 3
1 4
1 9 3 1
0 0

Output for the Sample Input

1
11
6



Sample input:
8 3
0 0 0 0 0 0 0 1
2 3 0 1 4 0 0 1
3 3 0 0 0 0 0 4
9 9 1 9
4 4
3 3 4 0
1 2 4 4
1 1 1 0
0 2 4 4
8 7 2 1
2 8
2 2
4 1
0 4
1 3
1 0
2 1
0 3
1 4
1 9 3 1
0 0


Sample output:
1
11
6

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
def inpl(): return list(map(int, input().split()))

W, H = inpl()
INF = 10**6

while W:
    S = [[5]*(W+2)]
    for _ in range(H):
        S.append([5] + inpl() + [5])
    S.append([5]*(W+2))
    C = inpl()
    D = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    E = [[[INF]*4 for _ in range(W+2)] for _ in range(H+2)]
    E[1][1][1] = 0
    Q = [[0, 1, (1, 1)]]
    while Q:
        e, d, (w, h) = heappop(Q)
        order = S[h][w]
        if e > E[h][w][d] or order == 5:
            continue

        dw, dh = D[d]
        ne = e + C[0]*(order != 0)
        if E[h+dh][w+dw][d] > ne:
            E[h+dh][w+dw][d] = ne
            heappush(Q, [ne, d, (w+dw, h+dh)])

        nd = (d+1)%4
        dw, dh = D[nd]
        ne = e + C[1]*(order != 1)
        if E[h+dh][w+dw][nd] > ne:
            E[h+dh][w+dw][nd] = ne
            heappush(Q, [ne, nd, (w+dw, h+dh)])

        nd = (d+2)%4
        dw, dh = D[nd]
        ne = e + C[2]*(order != 2)
        if E[h+dh][w+dw][nd] > ne:
            E[h+dh][w+dw][nd] = ne
            heappush(Q, [ne, nd, (w+dw, h+dh)])

        nd = (d+3)%4
        dw, dh = D[nd]
        ne = e + C[3]*(order != 3)
        if E[h+dh][w+dw][nd] > ne:
            E[h+dh][w+dw][nd] = ne
            heappush(Q, [ne, nd, (w+dw, h+dh)])

    print(min(E[H][W]))
    W, H = inpl()

Submission status: Accepted

Solution code:
# AOJ 1156: Twirling Robot
# Python3 2018.7.15 bal4u

mv = [[-1,0,],[0,1],[1,0],[0,-1]]

INF = 0x7fffffff
import heapq
def dijkstra(h, w, cost):
	Q = []
	node = [[[INF for d in range(4)] for c in range(w)] for r in range(h)]
	node[0][0][1] = 0
	heapq.heappush(Q, (0, 0, 0, 1))
	while Q:
		t, r, c, d = heapq.heappop(Q)
		if r == h-1 and c == w-1: break
		for i in range(4):
			nd = (d+i)%4
			nr, nc = r + mv[nd][0], c + mv[nd][1]
			if nr < 0 or nr >= h or nc < 0 or nc >= w: continue
			nt = node[r][c][d]
			if arr[r][c] != i: nt += cost[i]
			if nt < node[nr][nc][nd]:
				node[nr][nc][nd] = nt
				heapq.heappush(Q, (nt, nr, nc, nd))
	return node[h-1][w-1][d]
	
while True:
	w, h = map(int, input().split())
	if w == 0: break
	arr = [[] for r in range(h)]
	for r in range(h): arr[r] = list(map(int, input().split()))
	cost = list(map(int, input().split()))
	print(dijkstra(h, w, cost))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import heapq


class Tuple:
    def __init__(self, cost, y, x, dir):
        self.cost = cost
        self.y = y
        self.x = x
        self.dir = dir

    def __str__(self):
        return "y=" + str(self.y) + " : " + "x=" + str(self.x) + " : " + "dir=" + str(self.dir)

    def __cmp__(self, other):
        return self.cost - other.cost


dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def solve():
    X, Y = map(int, raw_input().split())
    if X == 0 and Y == 0:
        return -1

    stage = [map(int, raw_input().split()) for _ in range(Y)]
    C = map(int, raw_input().split())

    costs = [[[float("inf") for _ in xrange(4)] for _ in xrange(X)] for _ in xrange(Y)]

    costs[0][0][0] = 0
    queue = []

    heapq.heappush(queue, Tuple(0, 0, 0, 0))

    while len(queue) > 0:

        current = heapq.heappop(queue)
        if costs[current.y][current.x][current.dir] < current.cost:
            continue

        for operation in range(4):
            if operation == 0:
                # ????????? ?????£??´?????????

                next_dir = current.dir
            elif operation == 1:
                # ????????? ??????

                next_dir = (current.dir + 1) % 4
            elif operation == 2:
                # ????????? ?????¢

                next_dir = (current.dir + 2) % 4
            else:
                # ????????? ??????

                next_dir = (current.dir + 3) % 4
            # ????????? ??´????????????????????¢?????????????????????????????????????????\???????????¢??????????????????????????§???????????????

            next_x = current.x + dir_x[next_dir]
            next_y = current.y + dir_y[next_dir]
            next_cost = costs[current.y][current.x][current.dir]
            if stage[current.y][current.x] != operation:
                next_cost += C[operation]
            if 0 <= next_x < X and 0 <= next_y < Y:
                if costs[next_y][next_x][next_dir] > next_cost:
                    costs[next_y][next_x][next_dir] = next_cost
                    data = Tuple(next_cost, next_y, next_x, next_dir)
                    heapq.heappush(queue, data)

    return min(costs[Y - 1][X - 1])


if __name__ == '__main__':
    while True:
        result = solve()
        if result < 0:
            break

        print result

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import heapq


class Tuple:
    def __init__(self, cost, y, x, dir):
        self.cost = cost
        self.y = y
        self.x = x
        self.dir = dir


    def __cmp__(self, other):
        return self.cost - other.cost


dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def solve():
    X, Y = map(int, raw_input().split())
    if X == 0 and Y == 0:
        return -1

    stage = [map(int, raw_input().split()) for _ in range(Y)]
    C = map(int, raw_input().split())

    costs = [[[float("inf") for _ in xrange(4)] for _ in xrange(X)] for _ in xrange(Y)]

    costs[0][0][0] = 0
    queue = []

    heapq.heappush(queue, Tuple(0, 0, 0, 0))

    while len(queue) > 0:

        current = heapq.heappop(queue)
        if costs[current.y][current.x][current.dir] < current.cost:
            continue

        for operation in range(4):
            if operation == 0:
                # ????????? ?????£??´?????????

                next_dir = current.dir
            elif operation == 1:
                # ????????? ??????

                next_dir = (current.dir + 1) % 4
            elif operation == 2:
                # ????????? ?????¢

                next_dir = (current.dir + 2) % 4
            else:
                # ????????? ??????

                next_dir = (current.dir + 3) % 4
            # ????????? ??´????????????????????¢?????????????????????????????????????????\???????????¢??????????????????????????§???????????????

            next_x = current.x + dir_x[next_dir]
            next_y = current.y + dir_y[next_dir]
            next_cost = costs[current.y][current.x][current.dir]
            if stage[current.y][current.x] != operation:
                next_cost += C[operation]
            if 0 <= next_x < X and 0 <= next_y < Y:
                if costs[next_y][next_x][next_dir] > next_cost:
                    costs[next_y][next_x][next_dir] = next_cost
                    data = Tuple(next_cost, next_y, next_x, next_dir)
                    heapq.heappush(queue, data)

    return min(costs[Y - 1][X - 1])


if __name__ == '__main__':
    while True:
        result = solve()
        if result < 0:
            break

        print result

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**10
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 = []


    while True:
        w,h = LI()
        if h == 0:
            break
        a = [LI() for _ in range(h)]
        cs = LI()

        def search(s):
            d = collections.defaultdict(lambda: inf)
            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
                v[u] = True
                if u[0][0] == h-1 and u[0][1] == w-1:
                    return d

                for ui in range(4):
                    ud = cs[ui]
                    if a[u[0][0]][u[0][1]] == ui:
                        ud = 0
                    di,dj = dd[(u[1]+ui) % 4]
                    ni = u[0][0] + di
                    nj = u[0][1] + dj
                    if ni < 0 or ni >= h or nj < 0 or nj >= w:
                        continue
                    uv = ((ni,nj), (u[1]+ui) % 4)
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))
            return d

        d = search(((0,0), 1))
        r = inf
        for i in range(4):
            if r > d[((h-1,w-1),i)]:
                r = d[((h-1,w-1),i)]
        rr.append(r)

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



print(main())

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

def main():
  R, D, L, U = 0, 1, 2, 3
  vector = ((1, 0), (0, 1), (-1, 0), (0, -1))
  
  while True:
    w, h = map(int, input().split())
    if w == 0:
      break
    mp = [[5] + list(map(int, input().split())) + [5] for _ in range(h)]
    mp.insert(0, [5] * (w + 2))
    mp.append([5] * (w + 2))
    cost = list(map(int, input().split()))
    que = []
    heappush(que, (0, 1, 1, R))
    dic = {}
    dic[(1, 1, R)] = 0
    while que:
      total, x, y, direct = heappop(que)
      ins = mp[y][x]
      if ins == 5:
        continue
      if ins != 4:
        new_direct = (direct + ins) % 4
        vx, vy = vector[new_direct]
        nx, ny = x + vx, y + vy
        if not (nx, ny, new_direct) in dic or dic[nx, ny, new_direct] > total:
          dic[(nx, ny, new_direct)] = total
          heappush(que, (total, nx, ny, new_direct))
  
      for add_direct in range(4):
        new_direct = (direct + add_direct) % 4
        vx, vy = vector[new_direct]
        nx, ny = x + vx, y + vy
        if not (nx, ny, new_direct) in dic or dic[(nx, ny, new_direct)] > total + cost[add_direct]:
          dic[(nx, ny, new_direct)] = total + cost[add_direct]
          heappush(que, (total + cost[add_direct], nx, ny, new_direct))
    print(min(dic[(w, h, D)], dic[(w, h, R)]))

main()

Submission status: Accepted

Solution code:
import heapq

def main():

    w,h = 0,0
    grid = []
    c = []
    inf = 1000000007
    y = [0,1,0,-1]
    x = [1,0,-1,0]

    def inside(i,j):
        return 0<=i and i<h and 0<=j and j<w

    def solve():
        d = [[[inf]*4 for _ in range(w)] for _ in range(h)]
        d[0][0][0] = 0
        pq = [[0,0,0,0]]
        heapq.heapify(pq)
        while pq:
            ccost,cy,cx,cd = heapq.heappop(pq)
            if d[cy][cx][cd] < ccost: continue
            if cy==h-1 and cx==w-1:return ccost
            for i in range(4):
                nd = (cd+i)%4
                ny = cy+y[nd]
                nx = cx+x[nd]
                if not inside(ny,nx):continue 
                if i == grid[cy][cx]:ncost = ccost
                else                :ncost = ccost+c[i]
                if ncost<d[ny][nx][nd]:
                    d[ny][nx][nd] = ncost
                    heapq.heappush(pq,[ncost,ny,nx,nd])
        return inf

    while True:
        w,h = map(int,input().split())
        if w == 0:break
        grid = []
        for i in range(h):
            grid.append(list(map(int,input().split())))
        c = list(map(int,input().split()))
        print (solve())

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

def main():
    while True:
        w, h = map(int, input().split())
        if w == 0:
            break
        board = [list(map(int, input().split())) for i in range(h)]
        tmp = list(map(int, input().split()))
        p_cost = [tmp[2], tmp[3], tmp[0], tmp[1]]
        INF = int(1e5)
        mincost = [[[INF] * 4 for i in range(w)] for j in range(h)]
        q = deque()
        q.append((0, 0, 0, 3))
        while len(q) > 0:
            x, y, cost, from_ = q.popleft()
            # コストなしで進める方向
            if board[y][x] == 0:# 直進: (from_ + 2) % 4
                no_cost = (from_ + 2) % 4
            elif board[y][x] == 1:# 右折: (from_ + 3) % 4
                no_cost = (from_ + 3) % 4
            elif board[y][x] == 2:# 反転: from_
                no_cost = from_
            elif board[y][x] == 3:# 左折: (from_ + 1) % 4
                no_cost = (from_ + 1) % 4
            else:# 停止: なし
                no_cost = -1
            for i, (nx, ny) in enumerate([(x, y-1), (x+1, y), (x, y+1), (x-1, y)]):
                if i == no_cost:
                    next_cost = cost
                else:
                    next_cost = cost + p_cost[(i+4-from_)%4]
                if mincost[y][x][i] > next_cost:# 最小値を更新
                    mincost[y][x][i] = next_cost
                    # マスが存在する場合はqに入れる
                    if 0 <= nx and nx < w and 0 <= ny and ny < h:
                        q.append((nx, ny, next_cost, (i + 2) % 4))
        # print(mincost)
        print(min(mincost[h-2][w-1][2], mincost[h-1][w-2][1]))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def cal(x,y,a):
    return (x+y*W)*4 + a

def uncal(val):
    a = val%4
    vxy = val//4
    x,y = vxy%W, vxy//W
    return x,y,a

def dijkstra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0
    def search(s,w_0,q,weight):
        for t,w in lines[s]:
            w += w_0
            if weight[t] > w:
                heapq.heappush(q,[w,t])
                weight[t] = w
    q = [[0,s]]
    heapq.heapify(q)
    while q:
        w,n = heapq.heappop(q)
        search(n,w,q,weight)
    return weight



while True:
    W,H = inpl()
    if W==0 and H==0:
        break

    ss = [inpl() for _ in range(H)]
    cc = inpl() # 直進，右折，反転，左折

    dx = [0,1,0,-1]
    dy = [-1,0,1,0]
    lines = defaultdict(set)
    for x in range(W):
        for y in range(H):
            for a in range(4): # 向いてる方向
                s = cal(x,y,a)
                costs = cc[:]
                if ss[y][x] <= 3:
                    costs[ss[y][x]] = 0

                for st in range(4): # 進む向き (直進，右折，反転，左折)
                    ar = (a + st)%4
                    tx,ty = x+dx[ar],y+dy[ar]
                    if (0<=tx<W) and (0<=ty<H):
                        t = cal(tx,ty,ar)
                        lines[s].add((t,costs[st]))

    weights = dijkstra(lines,H*W*4,cal(0,0,1))
    #for y in range(H):
    #    for x in range(W):
    #        print(x,y,weights[cal(x,y,0):cal(x,y,3)+1])

    print(min(weights[cal(x,y,0):cal(x,y,3)+1]))

Submission status: Accepted

Solution code:
import sys
from collections import deque
from heapq import heappush,heappop

d = [(0,1),(1,0),(0,-1),(-1,0)]
def bfs():
    dist = [[[float("inf")]*4 for i in range(w)] for j in range(h)]
    dist[0][0][0] = 0
    q = [(0,0,0,0)]
    while q:
        dn,y,x,c = heappop(q)
        for di in range(4):
            c_ = ro[di][c]
            y_ = y+d[c_][0]
            x_ = x+d[c_][1]
            if 0 <= y_ < h and 0 <= x_ < w:
                if dist[y_][x_][c_] > dn+co[y][x][di]:
                    dist[y_][x_][c_] = dn+co[y][x][di]
                    heappush(q,(dist[y_][x_][c_],y_,x_,c_))
    return dist

while 1:
    w,h = map(int, sys.stdin.readline().split())
    if w == 0:
        break
    s = [list(map(int, sys.stdin.readline().split())) for i in range(h)]
    cost = list(map(int, sys.stdin.readline().split()))
    co = [[[cost[i] for i in range(4)] for x in range(w)] for y in range(h)]
    for y in range(h):
        for x in range(w):
            if s[y][x] < 4:
                co[y][x][s[y][x]] = 0
    ro = [[0]*4 for i in range(4)]
    for c in range(4):
        for i in range(4):
            if c == 0:
                ro[c][i] = i
            elif c == 1:
                ro[c][i] = (i+1)%4
            elif c == 2:
                ro[c][i] = (i+2)%4
            else:
                ro[c][i] = (i+3)%4

    dist = bfs()
    print(min(dist[h-1][w-1]))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import heapq


class Tuple:
    def __init__(self, cost, y, x, dir):
        self.cost = cost
        self.y = y
        self.x = x
        self.dir = dir

    def __str__(self):
        return "y=" + str(self.y) + " : " + "x=" + str(self.x) + " : " + "dir=" + str(self.dir) + ": cost=" + str(
            self.cost)


def solve():
    X, Y = map(int, raw_input().split())
    if X == 0 and Y == 0:
        return -1

    stage = [map(int, raw_input().split()) for _ in range(Y)]
    C = map(int, raw_input().split())

    memo = [[[10 ** 10 for _ in xrange(4)] for _ in xrange(X)] for _ in xrange(Y)]

    queue = []

    heapq.heappush(queue, Tuple(0, 0, 0, 0))

    dir_x = [1, 0, -1, 0]
    dir_y = [0, 1, 0, -1]

    while len(queue) > 0:

        current = heapq.heappop(queue)
        if memo[current.y][current.x][current.dir] > current.cost:
            memo[current.y][current.x][current.dir] = current.cost

            for operation in range(4):
                if operation == 0:
                    # ????????? ?????£??´?????????

                    next_dir = current.dir
                elif operation == 1:
                    # ????????? ??????

                    next_dir = (current.dir + 1) % 4
                elif operation == 2:
                    # ????????? ?????¢

                    next_dir = (current.dir + 2) % 4
                else:
                    # ????????? ??????

                    next_dir = (current.dir + 3) % 4
                # ????????? ??´????????????????????¢?????????????????????????????????????????\???????????¢??????????????????????????§???????????????

                next_x = current.x + dir_x[next_dir]
                next_y = current.y + dir_y[next_dir]
                next_cost = current.cost
                if stage[current.y][current.x] != operation:
                    next_cost += C[operation]
                if 0 <= next_x < X and 0 <= next_y < Y:
                    heapq.heappush(queue, Tuple(next_cost, next_y, next_x, next_dir))

    return min(memo[Y - 1][X - 1])


if __name__ == '__main__':
    while True:
        result = solve()
        if result < 0:
            break

        print result

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import heapq


class Tuple:
    def __init__(self, cost, y, x, dir):
        self.cost = cost
        self.y = y
        self.x = x
        self.dir = dir

    def __str__(self):
        return "y=" + str(self.y) + " : " + "x=" + str(self.x) + " : " + "dir=" + str(self.dir)


dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def solve():
    X, Y = map(int, raw_input().split())
    if X == 0 and Y == 0:
        return -1

    stage = [map(int, raw_input().split()) for _ in range(Y)]
    C = map(int, raw_input().split())

    costs = [[[float("inf") for _ in xrange(4)] for _ in xrange(X)] for _ in xrange(Y)]

    costs[0][0][0] = 0
    queue = []

    heapq.heappush(queue, Tuple(0, 0, 0, 0))

    while len(queue) > 0:

        current = heapq.heappop(queue)
        if costs[current.y][current.x][current.dir] < current.cost:
            continue

        for operation in range(4):
            if operation == 0:
                # ????????? ?????£??´?????????

                next_dir = current.dir
            elif operation == 1:
                # ????????? ??????

                next_dir = (current.dir + 1) % 4
            elif operation == 2:
                # ????????? ?????¢

                next_dir = (current.dir + 2) % 4
            else:
                # ????????? ??????

                next_dir = (current.dir + 3) % 4
            # ????????? ??´????????????????????¢?????????????????????????????????????????\???????????¢??????????????????????????§???????????????

            next_x = current.x + dir_x[next_dir]
            next_y = current.y + dir_y[next_dir]
            next_cost = costs[current.y][current.x][current.dir]
            if stage[current.y][current.x] != operation:
                next_cost += C[operation]
            if 0 <= next_x < X and 0 <= next_y < Y:
                if costs[next_y][next_x][next_dir] > next_cost:
                    costs[next_y][next_x][next_dir] = next_cost
                    data = Tuple(next_cost, next_y, next_x, next_dir)
                    heapq.heappush(queue, data)


    return min(costs[Y - 1][X - 1])

if __name__ == '__main__':
    while True:
        result = solve()
        if result < 0:
            break

        print result