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
|
import sys
import re
from copy import deepcopy
from math import gcd
from collections import defaultdict, Counter, deque
import heapq
import math
D = open(sys.argv[1]).read().strip()
L = D.split("\n")
G = [[c for c in row] for row in L]
R = len(G)
C = len(G[0])
sys.setrecursionlimit(10**6)
def solve(part1):
V = set()
for r in range(R):
for c in range(C):
nbr = 0
for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
nbr += 1
if nbr > 2 and G[r][c] != "#":
V.add((r, c))
for c in range(C):
if G[0][c] == ".":
V.add((0, c))
start = (0, c)
if G[R - 1][c] == ".":
V.add((R - 1, c))
end = (R - 1, c)
E = {}
for rv, cv in V:
E[(rv, cv)] = []
Q = deque([(rv, cv, 0)])
SEEN = set()
while Q:
r, c, d = Q.popleft()
if (r, c) in SEEN:
continue
SEEN.add((r, c))
if (r, c) in V and (r, c) != (rv, cv):
E[(rv, cv)].append(((r, c), d))
continue
for ch, dr, dc in [["^", -1, 0], ["v", 1, 0], ["<", 0, -1], [">", 0, 1]]:
if 0 <= r + dr < R and 0 <= c + dc < C and G[r + dr][c + dc] != "#":
if part1 and G[r][c] in ["<", ">", "^", "v"] and G[r][c] != ch:
continue
Q.append((r + dr, c + dc, d + 1))
count = 0
ans = 0
SEEN = [[False for _ in range(C)] for _ in range(R)]
seen = set()
def dfs(v, d):
nonlocal count
nonlocal ans
count += 1
r, c = v
if SEEN[r][c]:
return
SEEN[r][c] = True
if r == R - 1:
ans = max(ans, d)
for y, yd in E[v]:
dfs(y, d + yd)
SEEN[r][c] = False
dfs(start, 0)
return ans
print(solve(True))
print(solve(False))
|