20
https://adventofcode.com/2024/day/20
Prob
python
import sys
from queue import Queue
def run_maze(walls, st_pt):
dist = {}
que = Queue()
que.put((0, st_pt))
while not que.empty():
d, pt = que.get()
if pt in dist and dist[pt] <= d:
continue
dist[pt] = d
x, y = pt
for (dx, dy) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
npt = x + dx, y + dy
if npt not in walls and npt not in dist:
que.put((d + 1, npt))
return dist
def hdist(p1, p2) -> int:
x1, y1 = p1
x2, y2 = p2
return abs(x1 - x2) + abs(y1 - y2)
def main():
maze = []
for line in sys.stdin:
maze.append(line.strip())
st_pt = (0, 0)
ed_pt = (0, 0)
walls = set()
for x, line in enumerate(maze):
for y, ch in enumerate(line):
pt = (x, y)
if ch == '#':
walls.add(pt)
elif ch == 'S':
st_pt = pt
elif ch == 'E':
ed_pt = pt
dists = run_maze(walls, st_pt)
ans = 0
for p1, d1 in dists.items():
for p2, d2 in dists.items():
if d1 >= d2:
continue
hd = hdist(p1, p2)
if hd > 20:
continue
if d2 - d1 - (hd - 1) >= 100:
ans += 1
print(ans)
main()