<p>A certain bug&#39;s home is on the x-axis at position <code>x</code>. Help them get there from position <code>0</code>.</p>

<p>The bug jumps according to the following rules:</p>

<ul>
	<li>It can jump exactly <code>a</code> positions <strong>forward</strong> (to the right).</li>
	<li>It can jump exactly <code>b</code> positions <strong>backward</strong> (to the left).</li>
	<li>It cannot jump backward twice in a row.</li>
	<li>It cannot jump to any <code>forbidden</code> positions.</li>
</ul>

<p>The bug may jump forward <strong>beyond</strong> its home, but it <strong>cannot jump</strong> to positions numbered with <strong>negative</strong> integers.</p>

<p>Given an array of integers <code>forbidden</code>, where <code>forbidden[i]</code> means that the bug cannot jump to the position <code>forbidden[i]</code>, and integers <code>a</code>, <code>b</code>, and <code>x</code>, return <em>the minimum number of jumps needed for the bug to reach its home</em>. If there is no possible sequence of jumps that lands the bug on position <code>x</code>, return <code>-1.</code></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
<strong>Output:</strong> 3
<strong>Explanation:</strong> 3 jumps forward (0 -&gt; 3 -&gt; 6 -&gt; 9) will get the bug home.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
<strong>Output:</strong> -1
</pre>

<p><strong class="example">Example 3:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

from collections import deque

class Solution:
    def minimumJumps(self, forbidden: List[int], forward_step: int, backward_step: int, target: int) -> int:
        # Initialize a set of forbidden positions
        forbidden_set = set(forbidden)
      
        # Queue for breadth-first search with position and whether the last movement was forward (1) or backward (0)
        queue = deque([(0, 1)])
      
        # Visited set to keep track of positions and their last movement direction
        visited = {(0, 1)}
      
        # Step counter starting from 0
        steps = 0
      
        # Start breadth-first search
        while queue:
            # Process nodes level by level
            for _ in range(len(queue)):
                position, last_movement_forward = queue.popleft()
              
                # If the current position is the target, return the number of steps
                if position == target:
                    return steps
              
                # List of possible next positions
                next_positions = [(position + forward_step, 1)]  # always can go forward
              
                # Can only go backward if the last movement was forward
                if last_movement_forward:
                    next_positions.append((position - backward_step, 0))
              
                # Iterate over possible next positions
                for next_position, next_movement_forward in next_positions:
                    # Check if within bounds, not forbidden, and not already visited
                    if (0 <= next_position < 10000 and 
                        next_position not in forbidden_set and 
                        (next_position, next_movement_forward) not in visited):
                      
                        # Add to queue and mark as visited
                        queue.append((next_position, next_movement_forward))
                        visited.add((next_position, next_movement_forward))
          
            # Increment steps after finishing processing the current level
            steps += 1
      
        # Return -1 if it's not possible to reach the target
        return -1

140