Nan's Log

Problem Description#

There is a flea whose home is located at position x on a number line. Please help it reach its home starting from position 0.

The flea follows the following rules for jumping:

• 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 position in the forbidden array.
• The flea can jump beyond its home position, but it cannot jump to negative integers.

Given an integer array forbidden, where forbidden[i] represents a position that the flea cannot jump to, and integers a, b, and x, please return the minimum number of jumps the flea needs to reach its home. If there is no feasible solution to reach x exactly, return -1.

Example#

Example 1#

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: The flea can reach its home by jumping forward 3 times (0 -> 3 -> 6 -> 9).

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: The flea can reach its home by jumping forward once (0 -> 16), and then jumping back once (16 -> 7).

Constraints#

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000

All positions in the forbidden array are distinct.
Position x is not in the forbidden array.

Approach#

According to the problem description, we can first iterate through the forbidden array and record the positions that do not comply with the jumping rules. Then, based on the jumping rules and the flea's home position x, we can try to calculate the minimum number of jumps starting from 0. The specific approach is as follows:

• Iterate through the forbidden array and record the positions that do not comply with the jumping rules.
• Iterate through the forbidden array. For each position that does not comply with the jumping rules, record the distance it can be pushed forward.
• Iterate through the forbidden array. For each position, check if it complies with the jumping rules. If it does, we can calculate the minimum number of jumps for the flea to reach it. If it does not comply with the jumping rules, we do not need to calculate its jump count.
• Return the distance the positions that do not comply with the jumping rules can be pushed forward and the minimum number of jumps for the flea to reach them as the answer.

Code Example#

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

        if x==0:  return 0
        if x%math.gcd(a,b): return -1

        fb = set(forbidden)
        que = {(0,1)}
        visited = {(0,1)}
        step = 1
        mx = max(max(fb)+a+b,x+b)
        
        while que:
            que1 = set()
            for pos,back in que:
                pos1 = pos+a
                pos2 = pos-b
                if pos1==x or (back==0 and pos2==x): return step
                if pos1<=mx and pos1 not in fb and (pos1,0) not in visited:
                    visited.add((pos1,0))
                    que1.add((pos1,0))
                if back==0 and pos2>=0 and pos2 not in fb and (pos2,1) not in visited:
                    visited.add((pos2,1))
                    que1.add((pos2,1))
            que = que1
            step+=1
        return -1