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.

&nbsp;
Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -&gt; 3 -&gt; 6 -&gt; 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 -&gt; 16) then one jump backward (16 -&gt; 7) will get the bug home.


&nbsp;
Constraints:


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


class Solution:
    def minimumJumps(self, fb: List[int], a: int, b: int, x: int) -> int:
        fb = set(fb)
        q = deque([[0,0,True]])
        while(q):
            n,l,isf = q.popleft()
            if(n<0 or n in fb or n>2000+2*b):
                continue
            fb.add(n)
            if(n==x):
                return l
            if isf and n-b>0:
                q.append([n-b,l+1,False])                
            q.append([n+a,l+1,True])
        return -1
class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        
        // Visited Set
        Set<Integer> visited = new HashSet<Integer>();
        
        // Add forbidden coordinates to visited
        for (int i = 0; i < forbidden.length; i++) {
            visited.add(forbidden[i]);
        }
        
        // Distance/ Jumps map
        Map<Integer, Integer> jumps = new HashMap<>();
        jumps.put(0, 0);
        
        // BFS Queue
        Queue<Integer[]> q = new LinkedList<>();
        q.add(new Integer[] {0, 1});
        
        // BFS 
        while (q.size() != 0) {
            
            Integer[] ud = q.poll();
            
            int u = ud[0], d = ud[1];
            
            // x found
            if (u == x) {
                return jumps.get(u);
            }
            
            // jump right
            if (u + a < 6001 && !visited.contains(u+a)) {
                q.add(new Integer[] {u+a, 1});
                visited.add(u+a);
                jumps.put(u+a, jumps.get(u) + 1);
            }
            
            // jump left
            if (d != -1 && u - b > -1 && !visited.contains(u-b)) {
                q.add(new Integer[] {u-b, -1});
                jumps.put(u-b, jumps.get(u) + 1);
            }
            
        }
        
        return -1;
        
    }
}
class Solution
{
public:
    typedef pair<int, bool> pi;
    int minimumJumps(vector<int> &forbidden, int a, int b, int x)
    {
        set<int> st(forbidden.begin(), forbidden.end());
        vector<vector<int>> vis(2, vector<int>(10000, 0));
        vis[0][0] = 1;
        vis[1][0] = 1;
        queue<pi> q;
        q.push({0, true});
        int ans = 0;
        while (!q.empty())
        {
            int n = q.size();
            for (int i = 0; i < n; i++)
            {
                int curr = q.front().first;
                bool canJumpBackward = q.front().second;
                q.pop();
                if (curr == x)
                    return ans;
                int p1 = curr + a;
                int p2 = curr - b;
                if (p1 < 10000 && vis[0][p1] == 0 && st.find(p1) == st.end())
                {
                    q.push({p1, true});
                    vis[0][p1] = 1;
                }
                if (p2 >= 0 && vis[1][p2] == 0 && st.find(p2) == st.end() && canJumpBackward == true)
                {
                    q.push({p2, false});
                    vis[1][p2] = 1;
                }
            }
            ans++;
        }
        return -1;
    }
};
var minimumJumps = function(forbidden, a, b, x) {
    let f = new Set(forbidden);
    let m = 2000 + 2 * b;
    let memo = {};
    let visited = new Set();
    let res = dfs(0, true);
    return res === Infinity ? -1 : res;
    
    function dfs(i,canJumpBack) {
        if (i === x) return 0;
        let key = `${i},${canJumpBack}`;
        visited.add(i);
        if (memo[key] !== undefined) return memo[key];
        if (i > m || i < 0) return Infinity;
        let min = Infinity;
        if (canJumpBack && !f.has(i - b) && !visited.has(i-b)) {
            min = Math.min(min, 1 + dfs(i - b, false));
        }
        
        if (!f.has(i + a) && !visited.has(i+a)) {
            min = Math.min(min, 1 + dfs(i + a, true));
        }
        
        visited.delete(i);
        return memo[key] = min;
    }
};
Minimum Jumps to Reach Home