1654. Minimum Jumps to Reach Home #

Problem #

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.

Problem Statement #

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

The flea jumps according to the following rules:

It can jump exactly a positions forward (that is, jump to the right).
It can jump exactly b positions backward (that is, jump to the left).
It cannot jump backward 2 times consecutively.
It cannot jump to any position in the forbidden array.

The flea may jump forward beyond the position of its home, but it cannot jump to positions with negative integers. Given an integer array forbidden, where forbidden[i] is a position the flea cannot jump to, along with integers a, b, and x, return the minimum number of jumps needed for the flea to reach home. If there is no feasible plan that reaches exactly x, return -1.

Solution Approach #

Given coordinate x, a step length a for jumping forward, and a step length b for jumping backward. The task is to output the minimum number of jumps needed to get back home.
To find the minimum number of jumps, use BFS. The first plan that reaches coordinate x is the one with the minimum number of jumps. To handle forbidden, mark those positions as true in the memoization array. The restriction that it cannot jump backward 2 times in a row requires us to also record the jump direction when enqueuing in BFS. Each time it jumps backward, check whether the previous jump was backward; if it was, it cannot jump backward this time.

Code #

package leetcode

func minimumJumps(forbidden []int, a int, b int, x int) int {
	visited := make([]bool, 6000)
	for i := range forbidden {
		visited[forbidden[i]] = true
	}
	queue, res := [][2]int{{0, 0}}, -1
	for len(queue) > 0 {
		length := len(queue)
		res++
		for i := 0; i < length; i++ {
			cur, isBack := queue[i][0], queue[i][1]
			if cur == x {
				return res
			}
			if isBack == 0 && cur-b > 0 && !visited[cur-b] {
				visited[cur-b] = true
				queue = append(queue, [2]int{cur - b, 1})
			}
			if cur+a < len(visited) && !visited[cur+a] {
				visited[cur+a] = true
				queue = append(queue, [2]int{cur + a, 0})
			}
		}
		queue = queue[length:]
	}
	return -1
}