C++의 개구리 점프

<시간/>

강을 건너는 개구리가 있다고 가정해 봅시다. 강은 x 단위로 나뉘며 각 단위에는 돌이 있을 수 있습니다. 개구리는 돌 위에서는 뛸 수 있지만 물에서는 뛸 수 없습니다. 여기에 오름차순으로 정렬된 돌의 위치 목록이 있습니다. 개구리가 마지막 돌에 착지하여 강을 건널 수 있는지 여부를 확인해야 합니다. 처음에 개구리는 첫 번째 돌 위에 있고 첫 번째 점프는 1 유닛이어야 한다고 가정합니다.

개구리의 현재 점프가 k 단위였을 때 다음 점프는 k - 1, k 또는 k + 1 단위여야 합니다. 그리고 개구리는 앞으로만 점프할 수 있습니다.

따라서 주어진 배열이 [0,1,3,4,5,7,9,10,12]와 같으면 개구리는 1단위에서 두 번째 돌로, 2단위는 다음과 같이 참이 됩니다. 3번째 스톤, 그리고 다시 2 유닛은 4번째 스톤, 3 유닛은 6번째 스톤, 4 유닛은 7번째 스톤, 마지막으로 5 유닛은 8번째 스톤으로.

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

방문이라는 지도 정의
canCross() 함수를 정의하면 배열 스톤이 사용되며 pos는 0으로 초기화, k는 0으로 초기화,
키 :=pos OR(왼쪽 시프트 k 11비트)
방문한 키에 키가 있으면 -
- 방문 반품[키]
초기화 i의 경우:=pos + 1, i <돌의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- 갭 :=돌[i] - 돌[pos]
- 갭
- 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
갭> k + 1이면 −
- 방문함[key] :=false
- 거짓 반환
canCross(stones, i, gap) 함수 호출이 0이 아닌 경우 -
- 방문함[키] =사실
- 참을 반환

visited[key] =true 일 때 (pos는 돌의 크기와 동일 - 1) 그렇지 않으면 false

방문 반품[키]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   unordered_map < lli, int > visited;
   bool canCross(vector<int>& stones, int pos = 0, int k = 0) {
      lli key = pos | k << 11;
      if(visited.find(key) != visited.end())return visited[key];
      for(int i = pos + 1; i < stones.size(); i++){
         int gap = stones[i] - stones[pos];
         if(gap < k - 1)continue;
         if(gap > k + 1){
            return visited[key] = false;
         }
         if(canCross(stones, i, gap))return visited[key] = true;
      }
      return visited[key] = (pos == stones.size() - 1);
   }
};
main(){
   Solution ob;
   vector<int> v = {0,1,3,5,6,8,12,17};
   cout << (ob.canCross(v));
}

입력

0,1,3,5,6,8,12,17

C++의 개구리 점프

예시

입력

출력