1  from lib import *
 2  
 3  input = read_input(2018, 22)
 4  
 5  lines = input.splitlines()
 6  
 7  depth = int(lines[0].split()[1])
 8  
 9  tx, ty = map(int, lines[1].split()[1].split(","))
10  
11  
12  dp = {}
13  
14  
15  def get_geologic_index(x, y):
16      if (x, y) == (tx, ty):
17          return 0
18      if y == 0:
19          return x * 16807
20      if x == 0:
21          return y * 48271
22      if (x, y) not in dp:
23          dp[(x, y)] = get_erosion_level(x - 1, y) * get_erosion_level(x, y - 1)
24      return dp[(x, y)]
25  
26  
27  def get_erosion_level(x, y):
28      return (get_geologic_index(x, y) + depth) % 20183
29  
30  
31  print(sum(get_erosion_level(x, y) % 3 for y in range(ty + 1) for x in range(tx + 1)))
32  
33  
34  queue = [(0, 0, 0, 1)]
35  visited = set()
36  while queue:
37      d, x, y, e = heapq.heappop(queue)
38      if (x, y, e) in visited:
39          continue
40  
41      visited.add((x, y, e))
42      if (x, y, e) == (tx, ty, 1):
43          print(d)
44          break
45  
46      t = get_erosion_level(x, y) % 3
47      heapq.heappush(queue, (d + 7, x, y, (-e - t) % 3))
48      for p, q in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
49          if p < 0 or q < 0:
50              continue
51  
52          t = get_erosion_level(p, q) % 3
53          if t == e:
54              continue
55  
56          heapq.heappush(queue, (d + 1, p, q, e))