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
|
from sys import stdin
from math import lcm
from heapq import heappop, heappush
def tadd(a, b):
return (a[0] + b[0], a[1] + b[1])
# return tuple(map(sum, zip(a, b)))
def tmul(a, b):
return (a[0] * b, a[1] * b)
# return tuple([n*b for n in a])
def tmod(a, b):
return (a[0] % b[0], a[1] % b[1])
# return tuple([a%b for (a,b) in zip(a, b)])
def tdist(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
# direction tuple
def tdir(f):
return ([0, 1, 0, -1][f%4], [-1, 0, 1, 0][f%4])
data = stdin.readlines()
start = (data[0].index('.') - 1, -1)
end = (data[-1].index('.') - 1, len(data) - 2)
data = [l.strip()[1:-1] for l in data[1:-1]]
w = len(data[0])
h = len(data)
cycle = lcm(w, h)
# 0 N 1 E 2 S 3 W
blizzards = [set() for _ in range(4)]
for y, line in enumerate(data):
for x, c in enumerate(line):
dirs = "^>v<"
if c in dirs:
blizzards[dirs.index(c)].add((x, y))
def coll(x, y, t):
if (x, y) == start: return False
if (x, y) == end: return False
if not 0 <= x < w: return True
if not 0 <= y < h: return True
for d in range(4):
v = tmod(tadd((x, y), tmul(tdir(d), -t)), (w, h))
if v in blizzards[d]:
return True
return False
def search(start, end, t):
cur = [(0, (start, t))]
visited = set(cur[0][1])
def dist(node):
bv, t = node
return tdist(bv, end) + t
while True:
_, node = heappop(cur)
bv, t, = node
vs = [bv]
for d in range(4):
vs.append(tadd(bv, tdir(d)))
for v in vs:
if not coll(*v, t+1):
if v == end:
return t+1
node = (v, t+1)
if not node in visited:
visited.add(node)
heappush(cur, (dist(node), node))
partOne = search(start, end, 0)
print(partOne)
partTwo = search(start, end, search(end, start, partOne))
print(partTwo)
|
