-
Notifications
You must be signed in to change notification settings - Fork 162
/
818.py
21 lines (21 loc) · 791 Bytes
/
818.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def racecar(self, target):
q, cnt, used = [(0, 1)], 0, {(0, 1)}
while q:
new = []
for pos, speed in q:
if pos == target:
return cnt
elif pos > 20000 or -20000 > pos:
continue
if (pos + speed, speed * 2) not in used:
new.append((pos + speed, speed * 2))
used.add((pos + speed, speed * 2))
if speed > 0 and (pos, -1) not in used:
new.append((pos, -1))
used.add((pos, -1))
elif speed < 0 and (pos, 1) not in used:
new.append((pos, 1))
used.add((pos, 1))
q = new
cnt += 1