C++でのカエルジャンプ

川を渡っているカエルがいるとしましょう。川はxユニットに分割され、各ユニットに石がある場合があります。カエルは石の上でジャンプできますが、水ではジャンプできません。ここに、昇順で並べ替えられた石の位置のリストがあります。カエルが最後の石に着陸して川を渡ることができるかどうかを確認する必要があります。最初、カエルは最初の石の上にあり、最初のジャンプは1ユニットでなければならないと想定しています。

カエルの現在のジャンプがkユニットの場合、次のジャンプはk -1、k、またはk+1ユニットのいずれかである必要があります。そして、カエルは前方にしかジャンプできません。

したがって、与えられた配列が[0,1,3,4,5,7,9,10,12]のようである場合、答えは真になります。カエルは1ユニットから2番目の石にジャンプでき、2ユニットは3番目の石、次に2単位から4番目の石、3単位から6番目の石、4単位から7番目の石、最後に5単位から8番目の石。

これを解決するには、次の手順に従います-

• visitedという地図を定義する
• 関数canCross（）を定義します。これは配列の石を取り、posは0で初期化し、kは0で初期化します。
• key：=pos OR（左シフトk 11ビット）
• 訪問者にキーが存在する場合、-
  • 訪問した[キー]
  に戻る
• 初期化i：=pos + 1の場合、i <石のサイズの場合、更新（iを1増やします）、実行-
  • ギャップ：=stones [i] --stones [pos]
  • ギャップ
  • 次の部分を無視し、次の反復にスキップします
• ギャップ>k+ 1の場合、-
  • visited [key]：=false
  • falseを返す
• 関数canCross（stones、i、gap）を呼び出すとゼロ以外の場合、-
  • visited [key] =true
  • trueを返す

理解を深めるために、次の実装を見てみましょう-

例

#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

出力

1