16
https://adventofcode.com/2024/day/16
Prob1
python
import queue
import sys
from typing import Tuple
mat = []
for line in sys.stdin:
line = line.strip()
mat.append(line)
x_max = len(mat[0])
y_max = len(mat)
start = (0, 0)
end = (0, 0)
for x in range(x_max):
for y in range(y_max):
if mat[y][x] == 'S':
start = (x, y)
elif mat[y][x] == 'E':
end = (x, y)
dir_map = [(0, -1), (1, 0), (0, 1), (-1, 0)]
tab4 = [[[None]*x_max for y in range(y_max)] for d in range(4)]
que = queue.PriorityQueue()
def put_que(dis: int, pt: Tuple[int, int], dir):
v = tab4[dir][pt[1]][pt[0]]
if v and v <= dis:
return
que.put((dis, pt, dir))
tab4[dir][pt[1]][pt[0]] = dis
put_que(0, start, 1)
while not que.empty():
dis, pt, dir = que.get()
if tab4[dir][pt[1]][pt[0]] < dis:
continue
print(dis, pt, dir)
# rotate
put_que(dis + 1000, pt, (dir + 1)%4)
put_que(dis + 2000, pt, (dir + 2)%4)
put_que(dis + 1000, pt, (dir + 3)%4)
# forward
dx, dy = dir_map[dir]
nx, ny = pt[0] + dx, pt[1] + dy
if mat[ny][nx] in ['.', 'E']:
put_que(dis + 1, (nx, ny), dir)
ans = None
for d in range(3):
v = tab4[0][end[1]][end[0]]
if not v:
continue
if not ans or ans > v:
ans = v
print(ans)