#1654

Minimum Jumps to Reach Home

expert · 1125 · lc medium +32 · verified · 30.6% accepted · 1,562 likes · top 8%

⚑ DFS / BFS: Connected Components & Reachability

Description

A bug sits at position 0 on a number line and wants to reach position x. Each move is exactly a positions forward or b positions backward, but two consecutive backward moves are not allowed, and the bug cannot land on any forbidden position or go negative. Return the minimum number of jumps needed, or -1 if it is impossible.

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.

Code

1

2

3

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int: