1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
from collections import defaultdict
from sys import stdin
inp = [line.rstrip("\n") for line in stdin]
start = (inp[0].index("."), 0)
end = (inp[-1].index("."), len(inp) - 1)
def neighbours(
maze: list[str], prev: tuple[int, int], position: tuple[int, int]
) -> list[tuple[int, int]]:
ret = []
for dx in (-1, 1):
nx = position[0] + dx
if nx < 0 or nx >= len(maze[0]):
continue
if (nx, position[1]) == prev:
continue
c = maze[position[1]][nx]
if c == "#":
continue
if dx < 0 and c == ">" or dx > 0 and c == "<":
continue
ret.append((nx, position[1]))
for dy in (-1, 1):
ny = position[1] + dy
if ny < 0 or ny >= len(maze):
continue
if (position[0], ny) == prev:
continue
c = maze[ny][position[0]]
if c == "#":
continue
if dy < 0 and c == "v" or dy > 0 and c == "^":
continue
ret.append((position[0], ny))
return ret
to_explore: list[tuple[tuple[int, int], tuple[int, int]]] = [(start, (start[0], 1))]
edges: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict(set)
while to_explore:
root, pos = to_explore.pop()
prev = root
dist = 1
while True:
neighs = neighbours(inp, prev, pos)
if len(neighs) != 1 or inp[neighs[0][1]][neighs[0][0]] in "^>v<":
edges[root].add((dist, pos))
for n in neighs:
to_explore.append((pos, n))
break
dist += 1
prev = pos
pos = neighs[0]
def longest(
start: tuple[int, int],
goal: tuple[int, int],
seen: frozenset[tuple[int, int]],
edges: dict[tuple[int, int], set[tuple[int, tuple[int, int]]]],
) -> int | None:
if start == goal:
return 0
maximum = 0
new_seen = seen | {start}
for dist, n in edges[start]:
if n in seen:
continue
d = longest(n, goal, new_seen, edges)
if d is None:
continue
if d + dist > maximum:
maximum = d + dist
return maximum if maximum > 0 else None
print(longest(start, end, frozenset(), edges))
fullgraph: defaultdict[tuple[int, int], set[tuple[int, tuple[int, int]]]] = defaultdict(
set, ((k, v.copy()) for k, v in edges.items())
)
for k, v in edges.items():
for dist, pos in v:
fullgraph[pos].add((dist, k))
print(longest(start, end, frozenset(), fullgraph))
|
