Leetcode 1654 — Minimum Jumps to Reach Home
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.
Solution
The formulation of this problem is a standard search problem so the first step is to define a state. Obviously, the state should contain the position information. In additional to that, we also need to track if we can go backwards. As the objective is to calculate the minimum steps, we can include the number of steps in the state as well.
Therefore, we have the following definition:
State {
int position;
int step;
bool canGoBackwards;
}The initial state is State(0, 0, false) and the target state is State(targetPosition, ?, ?) and the problem becomes very similar to a shortest path search problem. One of the classic algorithms to solve this type of problems is BFS.
There is room for optimization because this problem has customized conditions. For example, instead of doing the layer-by-layer standard BFS, we can mix BFS with DFS (e.g. go as far as possible). Another optimization is that if State(position, step, true) is visited hen we can skip State(position, step, false) because we know it will not produce better results. (This is not implemented.)
One important question is when we can terminate the search and claim there is no solution. Note that all the input values are less than 2000. We can show that if the current position is larger than, for example 6000, then we can stop because continuing the search is pointless.
Suppose b>a
and b=ka+l with 0≤l<b. Then we can stop when the current position is larger than maximum forbidden position plus b plus l (i.e. beyond the red point in the figure below). The reason is that if the current position is beyond the red point, we can always go left by l unit distance because going backwards will not hit any forbidden positions. Therefore, if z≥max forbidden position+l+b and we can reach home from z, then we can also reach home from z−l.
