Thermostat Presses
Medium · graph traversal
An old thermostat shows a whole number of degrees, from 0 up to limit (both included). It has one button for each amount in the list shifts. Pressing a button adds its amount to the reading, so a negative amount lowers it. You can press the buttons in any order and as often as you like.
A press only works if the new reading is between 0 and limit (both included) and is not one of the readings in forbidden, where the heater trips. A press that would break either rule is simply not possible.
The display now shows start. Return the fewest presses needed to make it show target. If the display already shows target, the answer is 0. If target cannot be reached, return -1.
Examples
Example 1
Input: start = 2, target = 9, limit = 12, shifts = [3, -1], forbidden = []
Output: 5
Press +3 three times (5, 8, 11) and then -1 twice (10, 9). No route with fewer presses lands exactly on 9.
Example 2
Input: start = 0, target = 4, limit = 10, shifts = [2], forbidden = [2]
Output: -1
The only button adds 2, so the first press lands on 2, which is forbidden.
Example 3
Input: start = 5, target = 5, limit = 8, shifts = [1], forbidden = []
Output: 0
The display already shows the target.
Constraints
- 1 <= limit <= 2000
- 0 <= start <= limit and 0 <= target <= limit
- 1 <= len(shifts) <= 5, and each shift is not 0 and has absolute value at most limit
- 0 <= len(forbidden) <= limit, each forbidden reading is between 0 and limit, and neither start nor target is forbidden