Description
A robot starts at position 0 on an infinite number line. It can jump a steps forward or b steps backward. Some positions are forbidden. Return minimum number of jumps to reach position x, or -1 if impossible.
Examples
Input:
forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9Output:
3Explanation:
0->3->6->9
Input:
forbidden = [5,6,7,8], a = 4, b = 2, x = 6Output:
-1Explanation:
Position 6 is forbidden, so it's impossible to reach it. Even though it is possible to reach nearby positions like 4 (0->4) or 8 (0->4->8), position 6 itself cannot be visited.
Input:
forbidden = [10,20], a = 5, b = 3, x = 17Output:
4Explanation:
One optimal path is 0->5->10->7->12->17. Jumping forward to 5, then forward to position 10 (which is forbidden, so it is not possible to stop there), but it is possible to jump backward to 7, then forward to 12, and finally forward to 17.
Constraints
- •
1 ≤ forbidden.length ≤ 1000 - •
1 ≤ a, b, x ≤ 2000