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
|
from sys import stdin
from math import lcm
def tadd(a, b):
return tuple(map(sum, zip(a, b)))
def tmul(a, b):
return tuple([n*b for n in a])
def tmod(a, b):
return tuple([a%b for (a,b) in zip(a, b)])
# 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) - 3)
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 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():
cur = {(start, 0)}
frontier = set()
while True:
for bv, t in cur:
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
frontier.add((v, t+1))
cur = frontier
frontier = set()
return None
print(search() + 1)
|
