## 1654. 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 `a` positions forward (to the right).
• It can jump exactly `b` positions backward (to the left).
• It cannot jump backward twice in a row.
• It cannot jump to any `forbidden` positions.

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 the 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 = 9
Output: 3
Explanation: 3 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 = 11
Output: -1
```

Example 3:

```Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.
```

Constraints:

• `1 <= forbidden.length <= 1000`
• `1 <= a, b, forbidden[i] <= 2000`
• `0 <= x <= 2000`
• All the elements in `forbidden` are distinct.
• Position `x` is not forbidden.

## Rust Solution

``````struct Solution;

use std::collections::HashSet;
use std::collections::VecDeque;
use std::iter::FromIterator;

impl Solution {
fn minimum_jumps(forbidden: Vec<i32>, a: i32, b: i32, x: i32) -> i32 {
let mut visited: HashSet<(i32, bool)> = HashSet::new();
let mut queue: VecDeque<(i32, bool, i32)> = VecDeque::new();
let max_pos = forbidden.iter().max().unwrap_or(&0) + a + b + x;
let forbidden: HashSet<i32> = HashSet::from_iter(forbidden);
visited.insert((0, false));
queue.push_back((0, false, 0));
while let Some((pos, backjump, step)) = queue.pop_front() {
dbg!(pos);
if pos == x {
return step;
}
let next_pos = pos + a;
if next_pos <= max_pos
&& !forbidden.contains(&(next_pos))
&& visited.insert((next_pos, false))
{
queue.push_back((next_pos, false, step + 1));
}
if !backjump {
let next_pos = pos - b;
if next_pos >= 0
&& !forbidden.contains(&(next_pos))
&& visited.insert((next_pos, true))
{
queue.push_back((next_pos, true, step + 1));
}
}
}
-1
}
}

#[test]
fn test() {
let forbidden = vec![14, 4, 18, 1, 15];
let a = 3;
let b = 15;
let x = 9;
let res = 3;
assert_eq!(Solution::minimum_jumps(forbidden, a, b, x), res);
let forbidden = vec![8, 3, 16, 6, 12, 20];
let a = 15;
let b = 13;
let x = 11;
let res = -1;
assert_eq!(Solution::minimum_jumps(forbidden, a, b, x), res);
let forbidden = vec![1, 6, 2, 14, 5, 17, 4];
let a = 16;
let b = 9;
let x = 7;
let res = 2;
assert_eq!(Solution::minimum_jumps(forbidden, a, b, x), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.