Minimum Jumps to Reach Home
A certain bug's home is on the x-axis at position x. Help them get there from position 0.
The bug jumps according to the following rules:
- It can jump exactly
apositions forward to the right. - It can jump exactly
bpositions backward to the left. - It cannot jump backward twice in a row.
- It cannot jump to any
forbiddenpositions.
The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.
Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.
Example 1
Input
forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9Output
33 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.
Example 2
Input
forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11Output
-1There is no possible sequence of jumps that lands the bug on position 11.
Constraints
- 1 <= forbidden.length <= 1000
- 1 <= a, b, forbidden[i] <= 2000
- 0 <= x <= 2000
- All the elements in
forbiddenare distinct. - Position
xis not forbidden.