C ++中的Jump Game III
假设我们有一个非负整数arr的数组，我们最初位于数组的起始索引处。当我们出现在索引i处时，我们可以跳转到i+arr[i]或i-arr[i]，检查是否可以到达任何值为0的索引。我们要记住，我们不能跳到随时可以使用数组。因此，如果输入类似：arr=[4,2,3,0,3,1,2]并从5开始，则输出为true，因为移动5→4→1→3或5→6→4→1→3。
为了解决这个问题，我们将遵循以下步骤-
n：=arr的大小
定义队列q，将start插入q，定义一个称为visited的集合，并将start插入Visited的集合
当队列不为空时，
将curr-arr[curr]插入q
将curr-arr[curr]插入访问
将curr+arr[curr]插入q
将curr+arr[curr]插入访问
curr：=q的前元素，从q删除前元素
如果array[curr]为0，则返回true
如果curr+arr[curr]<n并且curr+arr[curr]不存在于访问集中，则
如果curr-arr[curr]>=0并且curr-arr[curr]在访问集中不存在，则
返回假
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
queue <int> q;
q.push(start);
set <int> visited;
visited.insert(start);
while(!q.empty()){
int curr = q.front();
q.pop();
if(arr[curr] == 0)return true;
if(curr + arr[curr] < n && !visited.count(curr + arr[curr])){
q.push(curr + arr[curr]);
visited.insert(curr + arr[curr]);
}
if(curr - arr[curr] >= 0 && !visited.count(curr - arr[curr])){
q.push(curr - arr[curr]);
visited.insert(curr - arr[curr]);
}
}
return false;
}
};
main(){
vector<int> v = {4,2,3,0,3,1,2};
Solution ob;
cout << (ob.canReach(v, 5));
}输入值
[4,2,3,0,3,1,2] 5
输出结果
1