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
|
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) - 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():
cur = {(start, 0, 0)}
frontier = set()
visited = set(cur)
while True:
for bv, t, gid 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):
new = None
if v == end and gid == 0:
new = (v, t+1, 1)
elif v == start and gid == 1:
new = (v, t+1, 2)
elif v == end and gid == 2:
return t+1
else:
new = (v, t+1, gid)
chk = (new[0], new[1] % cycle, new[2])
if not chk in visited:
visited.add(chk)
frontier.add(new)
cur = frontier
frontier = set()
return None
print(search())
|
