1
# Runtime: 95 ms (Top 46.38%) | Memory: 14.3 MB (Top 75.93%)
2
class Solution:
3
    def racecar(self, target: int) -> int:
4
        q = [(0, 1)]
5
        steps = 0
6

7
        while q:
8
            num = len(q)
9
            for i in range(num):
10
                pos, speed = q.pop(0)
11
                if pos == target:
12
                    return steps
13
                q.append((pos + speed, speed * 2))
14
                rev_speed = -1 if speed > 0 else 1
15
                if (
16
                    (pos + speed) < target
17
                    and speed < 0
18
                    or (pos + speed) > target
19
                    and speed > 0
20
                ):
21
                    q.append((pos, rev_speed))
22
            steps += 1