part2.py

from heapq import heapify, heappush, heappop


MOVES = ((0, 1), (0, -1), (1, 0), (-1, 0))

with open("input.txt") as file:
    cavern = [list(map(int, line)) for line in map(str.strip, file) if line]

size_y, size_x = len(cavern), len(cavern[0])
big_size_x, big_size_y = size_y * 5, size_x * 5

costs = [[None] * big_size_x for _ in range(big_size_y)]

pqueue = [(0, 0, 0)]
heapify(pqueue)

while pqueue:
    cost, row, col = heappop(pqueue)
    if costs[row][col] is not None:
        continue

    costs[row][col] = cost

    if row == big_size_x - 1 and col == big_size_y - 1:
        break

    for dy, dx in MOVES:
        new_row = row + dy
        new_col = col + dx
        if not (0 <= new_row < big_size_x and 0 <= new_col < big_size_y):
            continue

        a, b = divmod(new_row, size_y)
        c, d = divmod(new_col, size_x)

        heappush(pqueue, (cost + (cavern[b][d] + a + c - 1) % 9 + 1, new_row, new_col))

print(costs[-1][-1])