37 lines
1 KiB
Python
37 lines
1 KiB
Python
from lib import *
|
|
|
|
input = read_input(2022, 12)
|
|
|
|
|
|
grid = []
|
|
start = None
|
|
end = None
|
|
for i, line in enumerate(input.splitlines()):
|
|
grid.append([ord(c) - 97 if c not in "SE" else {"S": 0, "E": 25}[c] for c in line])
|
|
if "S" in line:
|
|
start = line.index("S"), i
|
|
if "E" in line:
|
|
end = line.index("E"), i
|
|
assert start and end
|
|
|
|
|
|
def bfs(start: tuple[int, int], grid, target, step):
|
|
queue: list[tuple[int, int, int]] = [(0, *start)]
|
|
visited = set()
|
|
while queue:
|
|
d, x, y = queue.pop(0)
|
|
|
|
if target(x, y):
|
|
return d
|
|
|
|
if (x, y) in visited:
|
|
continue
|
|
visited.add((x, y))
|
|
|
|
for p, q in get_neighbors(x, y, len(grid[0]), len(grid)):
|
|
if step(x, y, p, q) and (p, q) not in visited:
|
|
queue.append((d + 1, p, q))
|
|
|
|
|
|
print(bfs(start, grid, lambda x, y: (x, y) == end, lambda x, y, p, q: grid[q][p] - grid[y][x] <= 1))
|
|
print(bfs(end, grid, lambda x, y: grid[y][x] == 0, lambda x, y, p, q: grid[y][x] - grid[q][p] <= 1))
|