Leetcode 836 Solution

class Solution:
    def racecar(self, target: int) -> int:
        q = collections.deque()
        visited = set()

        q.append((0, 1))
        visited.add((0, 1))

        ans = 0
        while True:
            s = len(q)

            for _ in range(s):
                pos, speed = q.popleft()

                if pos == target:
                    return ans

                pos1, speed1 = pos + speed, 2 * speed
                if (pos1, speed1) not in visited and max(abs(pos1), abs(speed1)) <= 2 * target:
                    q.append((pos1, speed1))
                    visited.add((pos1, speed1))

                if speed > 0:
                    pos2, speed2 = pos, -1
                else:
                    pos2, speed2 = pos, 1

                if (pos2, speed2) not in visited:
                    q.append((pos2, speed2))
                    visited.add((pos2, speed2))

            ans += 1

        return ans