题解 | 棋盘游戏

import heapq


def dijkstra(grid, x, y, end_x, end_y):
    rows, cols = 6, 6
    visted = set()
    pq = [(0, x, y, 1)]

    while pq:
        cost, x, y, state = heapq.heappop(pq)

        if x == end_x and y == end_y:
            return cost
        if (x, y, state) in visted:
            continue
        visted.add((x, y, state))

        direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for dx, dy in direction:
            new_x, new_y = x + dx, y + dy

            if 0 <= new_x < 6 and 0 <= new_y < 6:
                step_cost = grid[new_x][new_y] * state
                new_state = (step_cost % 4) + 1
                heapq.heappush(pq, (cost+step_cost, new_x, new_y, new_state))
    return -1




grid = []
row = []
for i in range(6):
    a = list(map(int, input().split()))
    grid.append(a)
x, y, end_x, end_y = map(int, input().split())

print(dijkstra(grid, x, y, end_x, end_y))