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
|
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():
partOne = None
cur = [(0, (start, 0, 0))]
visited = set(cur[0][1])
asdf = 0
gid_bonus = tdist(start, end)
def dist(node):
bv, t, gid = node
goal = end if gid != 1 else start
score = 0
score += tdist(bv, goal)
score += t
score -= gid * gid_bonus
while True:
_, node = heappop(cur)
bv, t, gid = node
vs = [bv]
for d in range(4):
vs.append(tadd(bv, tdir(d)))
for v in vs:
if not coll(*v, t+1):
node = None
if v == end and gid == 0:
if not partOne: partOne = t+1
node = (v, t+1, 1)
elif v == start and gid == 1:
node = (v, t+1, 2)
elif v == end and gid == 2:
return partOne, t+1
else:
node = (v, t+1, gid)
chk = (node[0], node[1], node[2])
if not chk in visited:
visited.add(chk)
heappush(cur, (asdf, node))
asdf += 1
return None
print(search())
|
