C++ 中的青蛙跳跃
c++server side programmingprogramming更新于 2025/4/13 13:37:17
假设有一只青蛙正在过河。河流被分成 x 个单位，每个单位可能有一块石头。青蛙可以跳上石头，但不能跳到水面上。这里我们有一个按升序排列的石头位置列表，我们必须检查青蛙是否能够通过落在最后一块石头上过河。最初，青蛙在第一块石头上，假设第一次跳跃必须是 1 个单位。
当青蛙当前跳跃距离为 k 个单位时，它的下一次跳跃必须是 k - 1、k 或 k + 1 个单位。青蛙只能向前跳。
因此，如果给定的数组为 [0,1,3,4,5,7,9,10,12]，则答案为真，因为青蛙可以跳到距离第 2 个石块 1 个单位处，距离第 3 个石块 2 个单位处，然后再跳到距离第 4 个石块 2 个单位处，然后距离第 6 个石块 3 个单位处，距离第 7 个石块 4 个单位处，最后距离第 8 个石块 5 个单位处。
为了解决这个问题，我们将遵循以下步骤 −
- 定义一个名为 accessed 的映射
- 定义一个函数 canCross()，它将获取一个数组 stones，pos 用 0 初始化，k 用 0 初始化，
- key := pos OR (左移 k 11 位)
- 如果 key 存在于 accessed 中，则 −
- 返回visited[key]
- 初始化i := pos + 1，当i < 石头大小时，更新(将i增加1)，执行−
- gap := stones[i] - stones[pos]
- 如果gap < k - 1，则−
- 忽略以下部分，跳到下一次迭代
- 如果gap > k + 1，则−
- visited[key] := false
- 返回 False
- 如果调用函数 canCross(stones, i, gap) 非零，则−
- visited[key] = true
- 返回 True
- 当 pos 与 stone 的大小 - 1 相同时，visited[key] = true，否则为 false
- return visited[key]
让我们看看下面的实现以便更好地理解 −
示例
#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
