3

河流在宽度上分为 n 段，有石头或水 [1,0,0,1,1,0,1,1,0,1...]。河岸的一侧有一只乌龟，他可以以 x 的速度移动，x 速度意味着他可以一次越过河流的 x 段。在以 x 速度传中后，他可以获得这三种速度中的任何一种，x,x+1,x-1。他可以双向移动。

现在 1 代表石头，0 代表水。如果乌龟跳入水中他会死，但如果他在石头上跳跃，那么他可以根据给定的规则获得新的速度。

鉴于没有。段数 (n)、段分布 (array[n]) 和初始速度 (x)。发现乌龟有没有可能到达银行的另一边？

我已经递归地解决了这个问题，但不能使用非递归方法。

乌龟在一边||1,0,1,1,0,0,0,1,1,0,1,....||河的另一边

4

1 回答 1

3

基本上这是一个简单的搜索问题，你的状态是乌龟当前位置的元组和它的速度。它可以在不使用堆栈（深度优先）或队列（广度优先搜索）的情况下实现。这是在 Python 中使用队列的实现，即广度优先：

from collections import deque

def cross_river(river, position=0, speed=1):
    queue = deque([(position, speed, [])])
    visited = set()
    while queue:
        position, speed, path = queue.popleft()

        # if  last stone of river, return sequence of jumps to get there
        if position == len(river) - 1:
            return path

        # check whether we've been here before
        if (position, abs(speed)) in visited:
            continue
        visited.add((position, abs(speed)))

        # for all possible jumps, add the new state to the queue
        for i in [-1, 0, +1]:    # change in speed
            for k in [-1, +1]:   # change in direction
                new_spd = (speed + i) * k
                new_pos = position + new_spd
                if 0 <= new_pos < len(river) and river[new_pos] == 1:
                    queue.append((new_pos, new_spd, path + [new_spd]))

print cross_river([1,0,1,1,0,0,0,1,1,0,1])  # Result: [2, -2, 3, 4, 3]

（事实上​​，这个算法比你的问题中描述的更严格，因为乌龟必须准确地落在最后一块石头上，而不是另一边的任何地方，但这应该很容易改变。）

于 2013-09-12T10:13:28.177 回答