# 1306. Jump Game III

Given an array of non-negative integers `arr`, you are initially positioned at `start` index of the array. When you are at index `i`, you can jump to `i + arr[i]` or `i - arr[i]`, check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

``````Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3
``````

Example 2:

``````Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation: One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3
``````

Example 3:

``````Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.
``````

Constraints:

• `1 <= arr.length <= 5 * 104`
• `0 <= arr[i] < arr.length`
• `0 <= start < arr.length`

``````class Solution {
public:
bool canReach(vector<int>& arr, int start) {
int n = arr.size();
vector<bool> visited(n);
queue<int> q{{start}};
visited[start] = true;
while (!q.empty()) {
auto t = q.front(); q.pop();
if (arr[t] == 0) return true;
int left = t - arr[t], right = t + arr[t];
if (left >= 0 && !visited[left]) {
visited[left] = true;
q.push(left);
}
if (right < n && !visited[right]) {
visited[right] = true;
q.push(right);
}
}
return false;
}
};
``````

``````class Solution {
public:
bool canReach(vector<int>& arr, int start) {
if (start < 0 || start >= arr.size() || arr[start] < 0) return false;
if (arr[start] == 0) return true;
arr[start] = - arr[start];
return canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]);
}
};
``````

``````class Solution {
public:
bool canReach(vector<int>& arr, int start) {
return start >= 0 && start < arr.size() && arr[start] >= 0 && ((arr[start] = -arr[start]) == 0 || canReach(arr, start + arr[start]) || canReach(arr, start - arr[start]));
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1306

Jump Game

Jump Game II

Jump Game VII

https://leetcode.com/problems/jump-game-iii/

https://leetcode.com/problems/jump-game-iii/discuss/473221/Simple-Java-DFS-solution

https://leetcode.com/problems/jump-game-iii/discuss/465602/JavaC%2B%2BPython-1-Line-Recursion

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation