Minimum Jumps to Reach Home — BFS with State

Problem

A bug can jump forward a or backward b. Some positions are forbidden. Find minimum jumps from 0 to x.

Approach — BFS with direction state

State = (position, jumped_back). Avoid revisiting same (pos, back) state. Reasonable upper bound: x + b is max useful position.

Time: O(max_pos) | Space: O(max_pos)

Solutions

Python

from collections import deque
class Solution:
    def minimumJumps(self, forbidden: list[int], a: int, b: int, x: int) -> int:
        bad=set(forbidden)
        limit=max(x, max(forbidden))+a+b
        visited=set(); visited.add((0,False))
        q=deque([(0,False,0)])
        while q:
            pos,back,steps=q.popleft()
            if pos==x: return steps
            # forward
            npos=pos+a
            if npos<=limit and npos not in bad and (npos,False) not in visited:
                visited.add((npos,False)); q.append((npos,False,steps+1))
            # backward (only if didn't just jump back)
            if not back:
                npos=pos-b
                if npos>=0 and npos not in bad and (npos,True) not in visited:
                    visited.add((npos,True)); q.append((npos,True,steps+1))
        return -1

Complexity

Time: O(max_pos) | Space: O(max_pos)