Leetcode 1654. Minimum Jumps to Reach Home

[Wizmann]

题意

Problem

给一个数轴，需要从0点位置走到N点位置。数轴的范围是 0 ~ INF，也就是说可以走到大于N的点。

规定有一些点不可以走（雷区），记作forbidden[]。每一步可以向前走a步，或者向后走b步。

问最少需要多少步。

解法

本题是一道简单的最短路问题，可以使用BFS或者DFS来解。

唯一的难点在于如何估计在数轴上最大的位置。

考虑不可以走的点，那么至少需要走到max(forbidden) + 1的位置之后，才可以进行自由的调整。

那么我们走到的最大位置P一定有：

• P - b >= max(N, max(forbidden)
  因为向回走的话，一定不能走进雷区。
• 且P - a - b <= max(N, max(forbidden)
  但是如果少往前走a步的话，后退b步就会重新进入雷区

综上可得，P <= a + b + max(N, max(forbidden))

当然你也可以直接N * 4莽一把，只要不T就能过。