import heapq
from collections import deque

def solution(board):
    n = len(board)
    # 상, 우, 하, 좌
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    cost_board = [[[float('inf')] * 4 for _ in range(n)] for _ in range(n)]

    # 우선순위 큐 사용
    queue = []
    heapq.heappush(queue, (0, 0, 0, -1))  # 비용을 맨 앞에 두어 우선순위 결정

    while queue:
        cost, h, w, direction = heapq.heappop(queue)

        for d, (dh, dw) in enumerate(directions):
            h_new, w_new = h + dh, w + dw
            if direction != -1 and d == (direction + 2) % 4: continue # 역주행

            if 0 <= h_new < n and 0 <= w_new < n and board[h_new][w_new] == 0:
                cost_new = cost + 100
                if direction != -1 and direction != d:
                    cost_new += 500

                if cost_new <= cost_board[h_new][w_new][d]:
                    cost_board[h_new][w_new][d] = cost_new
                    heapq.heappush(queue, (cost_new, h_new, w_new, d))

    return min(cost_board[n - 1][n - 1])