检查Python是否可以通过左右跳到达数组的最右端

Question

我正在写一个程序，找出一个游戏是可解的还是不可解的。 游戏规则是：

1. 你从最左边的位置开始
2. 您可以根据位置处数组的值向左或向右跳跃，并且不能超出端点。例如：a={4,4,1,5,2,6,3,4,2,0}你从最左边的位置开始，这样你就可以从右边的4个位置跳到2个位置（左边是不可能的）

3. 我必须检查我们是否能到达另一端，它总是等于0。

4. 如果我们能到达最右边（即0），那么它是可解的，否则不可解

我试过在Python中使用递归，但不知道如何继续

 def KAuhop(b,c,d,current_position):
        position_move=b[current_position]
        if b[current_position+position_move]==0:
            print("found")
        else:
            KAuhop(b,current_position+position_move,d,current_position)
            print("Not found")




    a=[4,4,1,5,2,6,3,4,2,0]
    print(KAuhop(a,0,len(a)-1,0))

Answer 1

在这里，我们跟踪您在set对象中已经看到的位置：

In [25]: def kauhop(seq):
    ...:     seen = set()
    ...:     maxlen = len(seq) - 1
    ...:     def helper(pos):
    ...:         if pos > maxlen or pos < 0 or pos in seen:
    ...:             return False
    ...:         elif pos == maxlen:
    ...:             return True
    ...:         else:
    ...:             jump = seq[pos]
    ...:             seen.add(pos)
    ...:             left = helper(pos - jump)
    ...:             right = helper(pos + jump)
    ...:             return left or right
    ...:     return helper(0)
    ...:

In [26]: kauhop(a)
Out[26]: True

本质上，您可以使用递归来检查每个可能的路径。考虑您当前的位置：如果您在任一方向都超出了边界，或者您已经检查了该位置（它在seen），那么返回False。否则，按所见标记位置，检查左跳和右跳，如果左跳或右跳成功，则返回。注意：我使用了一个helper内部函数。这让我不必一直传递seen集，因为helper是在seen上闭合的，因此maxlen。你知道吗

现在我想知道是否有比暴力更好的方法。你知道吗