<p>Your car starts at position <code>0</code> and speed <code>+1</code> on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions <code>&#39;A&#39;</code> (accelerate) and <code>&#39;R&#39;</code> (reverse):</p>

<ul>
	<li>When you get an instruction <code>&#39;A&#39;</code>, your car does the following:

	<ul>
		<li><code>position += speed</code></li>
		<li><code>speed *= 2</code></li>
	</ul>
	</li>
	<li>When you get an instruction <code>&#39;R&#39;</code>, your car does the following:
	<ul>
		<li>If your speed is positive then <code>speed = -1</code></li>
		<li>otherwise <code>speed = 1</code></li>
	</ul>
	Your position stays the same.</li>
</ul>

<p>For example, after commands <code>&quot;AAR&quot;</code>, your car goes to positions <code>0 --&gt; 1 --&gt; 3 --&gt; 3</code>, and your speed goes to <code>1 --&gt; 2 --&gt; 4 --&gt; -1</code>.</p>

<p>Given a target position <code>target</code>, return <em>the length of the shortest sequence of instructions to get there</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> target = 3
<strong>Output:</strong> 2
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> target = 6
<strong>Output:</strong> 5
<strong>Explanation:</strong> 
The shortest instruction sequence is &quot;AAARA&quot;.
Your position goes from 0 --&gt; 1 --&gt; 3 --&gt; 7 --&gt; 7 --&gt; 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target &lt;= 10<sup>4</sup></code></li>
</ul>

# 你的赛车可以从位置 0 开始，并且速度为 +1 ，在一条无限长的数轴上行驶。
# 赛车也可以向负方向行驶。赛车可以按照由加速指令 'A' 和倒车指令 'R' 组成的指令序列自动行驶。

# 当收到指令 'A' 时，赛车这样行驶：
# position += speed
# speed *= 2

# 当收到指令 'R' 时，赛车这样行驶：
# 如果速度为正数，那么speed = -1
# 否则 speed = 1
# 当前所处位置不变。

#  "AAR" 后，赛车位置变化为 0 --> 1 --> 3 --> 3 ，速度变化为 1 --> 2 --> 4 --> -1 。

#  给你一个目标位置 target ，返回能到达目标位置的最短指令序列的长度。


# 解题思路：
# 题目要求找出从初始位置 0 开始，使用最短指令序列到达目标位置 target。你可以使用指令 A（加速）和 R（倒车）。
# 这本质上是一个广度优先搜索（BFS）问题，因为 BFS 能够保证找到最短路径。

# 分析：
# 指令 A：使汽车以当前速度前进，然后将速度加倍。
# 指令 R：使汽车停止并将速度反向，速度重置为 +1 或 -1。

# 我们可以将 BFS 用于探索所有可能的状态（位置和速度），并找到到达目标位置的最短指令序列。

# 步骤：
# 初始化 BFS 队列和集合来记录访问过的状态。每个状态可以表示为 (position, speed)。

# 从起点 (0, 1) 开始探索，每次移动都可以生成两种新状态：
# 执行指令 A，则移动到新位置并更新速度。
# 执行指令 R，则位置不变，速度反转为 +1 或 -1。

# 将所有新生成的状态添加到队列中，并记录当前步数。
# 如果在 BFS 过程中发现当前位置等于 target，则返回当前步数。


# set(position, speed)
# dq = deque([(position, speed, steps)])

from collections import deque
class Solution:
    def racecar(self, target: int) -> int:
        visited = set((0, 1))
        dq = deque([(0, 1, 0)])

        while dq:
            cur_position, cur_speed, steps = dq.popleft()

            if cur_position == target:
                return steps

            new_position, new_speed = cur_position + cur_speed, cur_speed * 2
            if (new_position, new_speed) not in visited and new_position <= 2 * target:
                visited.add((new_position, new_speed))
                dq.append((new_position, new_speed, steps + 1))

            new_position, new_speed = cur_position, -1 if cur_speed > 0 else 1
            if (new_position, new_speed) not in visited:
                visited.add((new_position, new_speed))
                dq.append((new_position, new_speed, steps + 1))

        
        return -1
194396