LeetCode 1654. The minimum number of jumps to get home one question per day

Problem description

There's a flea's home on the axis  x  It's about . Please help it from the position  0  set out , Get to its home .

The rules of flea jumping are as follows ：

It can forward Jump just right a  A place （ Jump right ）.
It can Back up   Jump just right b  A place （ Jump to the left ）.
It can't continuity Jump back 2 Time .
It can't jump to anything  forbidden  Position in array .
Fleas can jump forward exceed   The location of its home , But it is You can't jump to negative integers   The location of .

Give you an array of integers  forbidden , among  forbidden[i]  It's where fleas can't jump , At the same time give you the whole number  a, b  and  x , Please return to the flea's home for the minimum number of jumps . If it doesn't just arrive x  Feasible plan of , Please return -1 .

Example 1：

Input ：forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output ：3
explain ： Jump forward 3 Time （0 -> 3 -> 6 -> 9）, Fleas are 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
explain ： Jump forward once （0 -> 16）, And then jump back （16 -> 7）, Fleas are home .
 

Tips ：

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
forbidden  All the positions in are different from each other .
Location  x  be not in forbidden  in .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/minimum-jumps-to-reach-home
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        // Record the forbidden locations 
        Set<Integer> set = new HashSet<>();
        for(int forbid : forbidden) set.add(forbid);

        Queue<int[]> queue = new LinkedList<>();// The current position , Number of backward jumps 
        queue.offer(new int[]{0,0});
        boolean[][] visible = new boolean[8000][2];
        int ans = -1;
        while(!queue.isEmpty()){
            int size = queue.size();
            ans++;
            for(int i = 0;i < size;i++){
                int[] t = queue.poll();
                int position = t[0];
                if(position == x) return ans;
                int rollbackCount = t[1];
                if(visible[position][rollbackCount]) continue;
                visible[position][rollbackCount] = true;

                // Jump forward 
                if(position + a < 8000 && !set.contains(position + a)){
                    queue.offer(new int[]{position + a,0});
                }
                // Jump back 
                if(position - b >= 0 && !set.contains(position - b) && rollbackCount == 0){
                    queue.offer(new int[]{position - b,rollbackCount + 1});
                }
            }
        }
        return -1;
    }
}