1  from lib import *
 2  
 3  input = read_input(2022, 12)
 4  
 5  
 6  grid = []
 7  start = None
 8  end = None
 9  for i, line in enumerate(input.splitlines()):
10      grid.append([ord(c) - 97 if c not in "SE" else {"S": 0, "E": 25}[c] for c in line])
11      if "S" in line:
12          start = line.index("S"), i
13      if "E" in line:
14          end = line.index("E"), i
15  assert start and end
16  
17  
18  def bfs(start: tuple[int, int], grid, target, step):
19      queue: list[tuple[int, int, int]] = [(0, *start)]
20      visited = set()
21      while queue:
22          d, x, y = queue.pop(0)
23  
24          if target(x, y):
25              return d
26  
27          if (x, y) in visited:
28              continue
29          visited.add((x, y))
30  
31          for p, q in get_neighbors(x, y, len(grid[0]), len(grid)):
32              if step(x, y, p, q) and (p, q) not in visited:
33                  queue.append((d + 1, p, q))
34  
35  
36  print(bfs(start, grid, lambda x, y: (x, y) == end, lambda x, y, p, q: grid[q][p] - grid[y][x] <= 1))
37  print(bfs(end, grid, lambda x, y: grid[y][x] == 0, lambda x, y, p, q: grid[y][x] - grid[q][p] <= 1))