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