https://leetcode.com/problems/minimum-jumps-to-reach-home/
不那么容易提炼出思路的问题，没做出来，还是记录一下

个人解答

  1. class Solution:
  2.     def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
  3.         max_len = max(forbidden + [x]) + a + b
  4.         jumps = [0] + [math.inf] * max_len
  5.         for p in forbidden:
  6.             jumps[p] = -1
  8.         q = collections.deque([0])
  10.         while q:
  11.             curr = q.pop()
  12.             if curr + a <= max_len and jumps[curr + a] > jumps[curr] + 1:
  13.                 q.append(curr + a)
  14.                 jumps[curr + a] = jumps[curr] + 1
  15.             if curr - b > 0 and jumps[curr - b] > jumps[curr] + 1:
  16.                 jumps[curr - b] = jumps[curr] + 1
  17.                 if curr - b + a <= max_len and jumps[curr - b + a] > jumps[curr] + 2:
  18.                     q.append(curr - b + a)
  19.                     jumps[curr - b + a] = jumps[curr] + 2
  21.         return jumps[x] if jumps[x] < math.inf else -1

参考：https://leetcode.com/problems/minimum-jumps-to-reach-home/discuss/935419/Python-deque-BFS-O(max(x-max(forbidden))%2Ba%2Bb))%2Ba%2Bb))

题目分析

模拟回溯是最容易想到的，但是其实这本身转换一下就是个最短路径的问题啊！！为什么没有想到呢？

这个题目有两个要点需要注意，也不是那么容易想清楚的

一个在于，不能连续两次后退如何记录。最容易想到的就是，记录到达位置的时候，同时记录方向，这样根据前一个方向判断是不是能再向后跳。
当然，这是比较naive的做法了，自己参考的这个解法，就比较精妙了，对于后跳的位置，下一步肯定不能再后跳了，直接考虑后跳再前跳的结果就是了。也就是说，合法的跳转，不是原来的向前和向后，而是 向前 和 向后再向前。如此一来，就不用考虑题目限制了，妙！

另一个在于，确定最远的跳的位置，也就是答案中的：

  1. max_len = max(forbidden + [x]) + a + b

forbidden中的元素和x这些位置肯定要涵盖进来，不然要丢失信息，可能出错。
但是，还要加上a+b。这个在原discussion中讲的挺清楚的，也就是，要能够在上述位置中最大位置之后，依然有足够的空间可以通过前跳和后跳到达任意位置。
举一个比较极端的情况：
a = 3, b = 7, x = 1, forbidden = [2]
那么路线：0 3 6 9 12 5 8 1
最远需要到12这个位置

整体还是很值得学习的。