当某些点被阻挡时到达终点的最小跳跃

Question

一个人目前在(0,0)并想要到达(X,0)，他必须跳几步才能到达他的房子。从一个点来说(a,0)，他可以跳到(a + k1,0)前面的k1步骤，也可以跳到(a-k2,0)后面的k2步骤。第一次跳必须是向前跳。而且，他不能连续两次向后跳。但是他可以跳任何一个连续向前a1,a2 upto an跳。有n个点是他不能跳的。

我必须确定到达他家的最少跳跃次数或得出他无法到达他家的结论。如果他可以到达房屋打印是并指定否。跳数 如果不打印没有。

这里

X = location of persons house.
N = no. of points where he cannot jump.
k1 = forward jump.
k2 = backward jump.

例子

对于输入

X=6 N=2 k1=4 k2=2

Blocked points = 3 5

the answer is 3 (4 to 8 to 6 or 4 to 2 to 6)

对于输入

6 2 5 2

1 3

这个人无法到达他的家

N can be upto 10^4 and X can be upto 10^5

我想过使用动态编程，但我无法实现它。任何人都可以帮忙吗？

Answer 1

我认为你使用动态编程的方向是可行的，但我将展示另一种方法来解决问题，其渐近时间复杂度与动态编程所实现的相同。

这个问题可以描述为图中的问题，其中您有索引到的节点X，并且这些节点是每个和之间的边，并且您在其中删除了节点。 如果您可以向后跳多少次，但不能连续跳两次，那么这就足够了，因此您可以添加以下修改：复制图形的节点，也复制向前的边，但使它们从复制的到原来的，现在使所有向后的边都转到复制的图。现在，每个后向边缘都会将您发送到重复的边缘，并且您将无法再次使用后向边缘，直到您使用前向边缘转到原始边缘。这将确保在向后边缘之后您将始终占据向前边缘 - 因此您将无法向前跳跃两次。1Xaa + k1bb - k2N

1现在找到从到 的最短路径X就像找到最小数量的跳跃一样，因为边缘是跳跃。

在有向未加权图中查找最短路径需要O(|V|+|E|)时间和内存（使用BFS），您的图具有2 * Xas|V|并且边的数量将是2 * 2 * X的时间和内存复杂度O(X)。

如果您可以向后跳转两次，则可以使用networkxpython 中的库进行简单演示（也可以使用 if 进行复杂演示）：

import matplotlib.pyplot as plt
import networkx as nx

X = 6
N = 2
k1 = 4
k2 = 2

nodes = [0, 1, 2, 4, 6]

G = nx.DiGraph()
G.add_nodes_from(nodes)

for n in nodes:
    if n + k1 in nodes:
        G.add_edge(n, n + k1)
    if n - k2 in nodes:
        G.add_edge(n, n - k2)

nx.draw(G, with_labels=True, font_weight='bold')
plt.plot()
plt.show()

path = nx.shortest_path(G, 0, X)
print(f"Number of jumps: {len(path) - 1}. path: {str(path)}")