C++의 자동차 경주

<시간/>

위치 0에서 시작하여 무한 수선에서 속도가 +1인 자동차가 있다고 가정합니다. 자동차는 일련의 지침 A:가속 및 R - 후진에 따라 자동으로 실행됩니다. 지시 "A"를 받으면 우리 차는 다음을 수행합니다 -

위치 :=위치 + 속도, 그 다음 속도 =속도 * 2.

명령 "R"을 받으면 우리 차는 다음을 수행합니다. -

속도가 양수이면 속도 =-1,
그렇지 않으면 속도 =1입니다.

예를 들어, "AAR" 명령을 실행한 후 우리 차는 위치 0->1->3->3으로 이동하고 속도는 1->2->4->-1로 이동합니다.

이제 목표 위치가 있다고 가정합니다. 거기에 도달하려면 가장 짧은 명령어 시퀀스의 길이를 찾아야 합니다.

따라서 입력이 target =6과 같으면 가능한 시퀀스 중 하나가 AAARA이고 위치 시퀀스는 0->1->3->7->7->6

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

방문 한 세트 정의
하나의 대기열 q 정의
q에 { 0, 1 } 삽입
초기화 레벨의 경우:=0, q가 비어 있지 않은 경우 업데이트(레벨 1 증가), 수행 -
- 초기화 k의 경우:=q의 크기, k> 0일 때 업데이트(k를 1만큼 감소), 수행 -
  - 한 쌍의 curr 정의:=q의 앞 요소, q에서 요소 삭제
  - curr의 첫 번째가 target과 같으면 -
    - 반환 수준
  - forward :=curr의 첫 번째 + curr의 두 번째
  - forwardSpeed :=현재의 초 * 2
  - key :=문자열로 순방향 변환 연결 " * " 연결 forwardSpeed를 문자열로 연결
  - 앞으로> 0 및 |앞으로 - 대상|
  - 방문한 항목에 키 삽입
  - q에 { forward, forwardSpeed } 삽입
- key :=첫 번째 curr을 문자열로 변환 concatenate " * "는 두 번째 curr> 0일 때 0을 연결하고, 그렇지 않으면 -1
- curr.first> 0 및 |target - curr.first|인 경우 <타겟과 키가 방문되지 않은 경우 −
  - 방문한 항목에 키 삽입
  - { curr.first, (curr.second> 0이면 -1, 그렇지 않으면 1 }) q에 삽입

반환 -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));
}

C++의 자동차 경주

예

입력

출력