1654.md

1654. Minimum Jumps to Reach Home

Solution 1 (time O(max(max(forbidden) + a, x) + b), space O(max(max(forbidden) + a, x) + b))

# BFS
class Solution(object):
    def minimumJumps(self, forbidden, a, b, x):
        """
        :type forbidden: List[int]
        :type a: int
        :type b: int
        :type x: int
        :rtype: int
        """
        q, visited = deque([[0, 1, 0]]), set([0])
        lower, upper = 0, max(max(forbidden) + a, x) + b
        forbiddenSet = set(forbidden)
        while q:
            position, direction, step = q.popleft()
            if position == x:
                return step
            nextPosition = position + a
            nextDirection = 1
            if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                visited.add(nextPosition * nextDirection)
                q.append([nextPosition, nextDirection, step + 1])
            if direction == 1:
                nextPosition = position - b
                nextDirection = -1
                if lower <= nextPosition <= upper and nextPosition * nextDirection not in visited and nextPosition not in forbiddenSet:
                    visited.add(nextPosition * nextDirection)
                    q.append([nextPosition, nextDirection, step + 1])
        return -1