1654. 到家的最少跳跃次数

Difficulty
Medium
Tags
BFS
URL
https://leetcode-cn.com/problems/minimum-jumps-to-reach-home/
Star
有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
跳蚤跳跃的规则如下：
  • 它可以 往前 跳恰好 a 个位置（即往右跳）。
  • 它可以 往后 跳恰好 b 个位置（即往左跳）。
  • 它不能 连续 往后跳 2 次。
  • 它不能跳到任何 forbidden 数组中的位置。
跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰好到达 x 的可行方案，请你返回 -1 。
示例 1：
输出：3
解释：往前跳 3 次（0 -> 3 -> 6 -> 9），跳蚤就到家了。
示例 2：
输入：forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
输出：-1
示例 3：
输入：forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
输出：2
解释：往前跳一次（0 -> 16），然后往回跳一次（16 -> 7），跳蚤就到家了。
提示：
  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • forbidden 中所有位置互不相同。
  • 位置 x 不在 forbidden 中。

法 1 BFS

思路
注意回退的时候不能放到visited中，
放到visited中的点意味着不用从这个点再开始扩散了，但是本题由于回退的次数限制，所以第一次回退的点之后可能还会被用来扩散。
题解
class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        forbidden = set(forbidden)
        Q = deque()
        Q.append((0, 0, True))
        while Q:
            cur, step, is_back = Q.popleft()
            if cur == x:
                # 第一次到x即最小步数，
                # 因为队列后序元素cnt都是大于等于当前cnt的
                return step

            next_loc = cur + a 
            if next_loc < 6000 and next_loc not in forbidden:
                # 6000是往右探索的最大值，x最大为2000
                forbidden.add(next_loc)
                Q.append((next_loc, step+1, True))
            
            next_loc = cur - b 
            if is_back and next_loc > 0 and next_loc not in forbidden:
                # forbidden.add(next_loc) 
                # 这里不能forbidden，因为后退回cur-b处时，
                # 无法覆盖前进到cur-b再后退到cur-2b的情况
                Q.append((next_loc, step+1, False))
        
        return -1
队列中存储 is_back 很合理，不过次数step没必要也同时放到队列中，因为队列中的都是同样的step.
class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        if x == 0:
            return 0
        
        forbidden = set(forbidden)
        if x in forbidden:
            return -1

        queue = deque()
				# 当前位置，下一步是否可以向后
        queue.append((0, True))
        
        visited = set()
        visited.add(0)

        step = -1
        while queue:
            step += 1
            size = len(queue)
            while size > 0:
                cur_loc, is_back = queue.popleft()
                size -= 1
                
                if cur_loc == x:
                    return step
                
                # 向前
                right = cur_loc + a
                if right <= 6000 and right not in visited and right not in forbidden:
                    visited.add(right)
                    queue.append((right, True))
                
                # 向后
                if is_back:
                    left = cur_loc - b
                    if left >= 0 and left not in visited and left not in forbidden:
                        queue.append((left, False))

        return -1