1  from lib import *
 2  
 3  input = read_input(2021, 15)
 4  
 5  lines = input.splitlines()
 6  
 7  
 8  def dijkstra(k):
 9      grid = [[*map(int, line)] for line in lines]
10      w = len(grid[0])
11      h = len(grid)
12      queue = [(0, 0, 0)]
13      visited = set()
14      while queue:
15          d, x, y = heapq.heappop(queue)
16  
17          if (x, y) in visited:
18              continue
19  
20          visited.add((x, y))
21  
22          if (x, y) == (w * k - 1, h * k - 1):
23              return d
24  
25          for p, q in get_neighbors(x, y, w * k, h * k):
26              c = grid[q % h][p % w] + q // h + p // w
27              c = (c - 1) % 9 + 1
28              heapq.heappush(queue, (d + c, p, q))
29  
30  
31  print(dijkstra(1))
32  print(dijkstra(5))