C ++中的青蛙跳

假设有一只青蛙过河。河流分为x个单位，每个单位可能有一块石头。青蛙可以在石头上跳，但不能跳水。在这里，我们按升序排列了石头的位置列表，我们必须检查青蛙是否能够通过降落在最后一块石头上来渡河。最初，青蛙在第一块石头上，并假设第一跳必须为1单位。

当青蛙的当前跳跃为k单位时，则其下一个跳跃必须为k-1，k或k + 1单位。青蛙只能向前跳。

因此，如果给定的数组像[0,1,3,4,5,7,9,10,12]，那么答案将是正确的，因为青蛙可以跳到1单位到2nd石头，2个单位到第三块石头，然后再次是2个单位到第四块石头，然后是3个单位到第六块石头，然后是4个单位到第七块石头，最后是5个单位到第八块石头。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个称为Visited的映射

• 定义一个函数canCross()，它将得到一个数组stone，pos用0初始化，k用0初始化，

• 键：= pos OR（左移k 11位）

• 如果访问者中存在键，则-

• 返回访问[关键]

• 对于初始化i：= pos + 1，当i <宝石大小时，更新（将i增加1），执行-

• Visited [key] = true

• 返回真

• Visited [key]：= false

• 返回假

• 忽略以下部分，跳至下一个迭代

• 间隙：=石头[i]-石头[pos]

• 如果gap <k-1，则-

• 如果差距> k + 1，则-

• 如果调用函数canCross(stones,i,gap)为非零，则-

• visit [key] =当（位置与石头的大小相同-1）时为true，否则为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

输出结果

1