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: BFS
Normal BFS with two tricks:
1. For each position, we need to track whether it’s reached via a forward jump or backward jump
2. How far should we go? If we don’t limit, it can go forever which leads to TLE/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that’s maximum distance we can jump back to home in one shot.
Time complexity: O(max_distance * 2)
Space complexity: O(max_distance * 2)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class Solution { public: int minimumJumps(vector<int>& forbidden, int a, int b, int x) { constexpr int kMaxPosition = 4000; if (x == 0) return 0; queue<pair<int, bool>> q{{{0, true}}}; unordered_set<int> seen1, seen2; for (int f : forbidden) seen1.insert(f), seen2.insert(f); seen1.insert(0); int steps = 0; while (!q.empty()) { int size = q.size(); while (size--) { auto [cur, forward] = q.front(); q.pop(); if (cur == x) return steps; if (cur > kMaxPosition) continue; // no way to go back if (seen1.insert(cur + a).second) q.emplace(cur + a, true); if (cur - b >= 0 && forward && seen2.insert(cur - b).second) q.emplace(cur - b, false); } ++steps; } return -1; } }; |