Formatted question description: https://leetcode.ca/all/1654.html

1654. Minimum Jumps to Reach Home

Level

Medium

Description

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

  • 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 forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

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.

Constraints:

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • All the elements in forbidden are distinct.
  • Position x is not forbidden.

Solution

If x == 0, return 0.

Use a set to store all forbidden positions, and then do breadth first search. Since each position can be reached from either the forward direction or the backward position, use a positive number to represent the forward direction and use a negative number to represent the backward direction. Use another set to store all visited positions.

Each time obtain the current position and the direction, and obtain the next positions and the corresponding directions. If the next positions are not forbidden and have not been visited with the corresponding directions, then the next positions are to be visited in the next step. Once x is reached, return the number of jumps. Since the range of positions is limited, if a position is beyond some value, then do not consider it. If x is never reached, return -1.

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        if (x == 0)
            return 0;
        Set<Integer> forbiddenSet = new HashSet<Integer>();
        for (int num : forbidden)
            forbiddenSet.add(num);
        Set<Integer> visited = new HashSet<Integer>();
        visited.add(0);
        int jumps = 0;
        Queue<int[]> queue = new LinkedList<int[]>();
        queue.offer(new int[]{0, 1});
        while (!queue.isEmpty()) {
            jumps++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] array = queue.poll();
                int position = array[0], direction = array[1];
                int nextPosition1 = position + a, nextPosition2 = position - b;
                if (nextPosition1 == x)
                    return jumps;
                else if (nextPosition1 <= 40000 && !visited.contains(nextPosition1) && !forbiddenSet.contains(nextPosition1)) {
                    visited.add(nextPosition1);
                    queue.offer(new int[]{nextPosition1, 1});
                }
                if (direction > 0 && nextPosition2 >= 0) {
                    if (nextPosition2 == x)
                        return jumps;
                    else if (!visited.contains(nextPosition2) && !forbiddenSet.contains(nextPosition2)) {
                        visited.add(-nextPosition2);
                        queue.offer(new int[]{nextPosition2, -1});
                    }
                }
            }
        }
        return -1;
    }
}

All Problems

All Solutions