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初始化，
键：=posOR（左移k11位）
如果访问者中存在键，则-
返回访问[关键]
对于初始化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