C ++中的赛车
假设我们有一辆汽车，它在无穷编号线上的位置0开始，速度+1。赛车会按照以下说明自动运行：A：加速，R-反向。当我们收到指令“A”时，我们的汽车将执行以下操作：
位置：=位置+速度，然后速度=速度*2。
当我们收到指令“R”时，我们的汽车将执行以下操作：
如果速度为正，则速度=-1，
否则速度=1。
例如，执行完“AAR”指令后，我们的汽车将转到位置0->1->3->3，速度将变为1->2->4->-1。
现在假设我们有一些目标位置。我们必须找到最短指令序列的长度才能到达那里。
因此，如果输入类似于target=6，则输出将为5，因为可能的序列之一是AAARA，位置序列将为0->1->3->7->7->6
为了解决这个问题，我们将遵循以下步骤-
定义一组参观
定义一个队列q
将{0，1}插入q
对于初始化级别：=0，如果非q为空，则更新（将级别增加1），执行-
定义一对curr：=q的前元素，从q删除元素
如果第一个与目标相同，则-
前进：=当前第一个+当前第二个
forwardSpeed：=当前秒*2
键：=将正向转换为字符串并置“*”将并转正向速度转换为字符串
如果正向>0且|正向-目标|<没有访问目标和非键，则-
key：=将curr的第一个转换为字符串连接“*”，当curr的第二个>0时连接0，否则为-1
如果curr.first>0并且|target-curr.first|<未访问目标和键，则-
回报水平
将键插入已访问
将{forward，forwardSpeed}插入q
将键插入已访问
将{curr.first（如果curr.second>0，然后是-1，否则为1}）插入q
对于初始化k：=q的大小，当k>0时，更新（将k减1），执行-
返回-1
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int racecar(int target) {
unordered_set < string > visited;
queue < pair <int ,int> > q;
q. push({0, 1});
for(int level = 0; !q.empty(); level++){
for(int k = q.size(); k > 0; k-- ){
pair <int, int> curr = q.front();
q.pop();
if(curr.first == target) return level;
int forward = curr.first + curr.second;
int forwardSpeed = curr.second * 2;
string key = to_string(forward) + "*" + to_string(forwardSpeed);
if(forward > 0 && abs(forward - target) < target && !visited.count(key)){
visited.insert(key);
q.push({forward, forwardSpeed});
}
key = to_string(curr.first) + "*" + to_string(curr.second > 0 ? - 1: 1);
if(curr.first > 0 && abs(target - curr.first) < target && !visited.count(key)){
visited.insert(key);
q.push({curr.first, curr.second > 0 ? - 1: 1});
}
}
}
return -1;
}
};
main(){
Solution ob;
cout << (ob.racecar(6));
}输入值
6
输出结果
5