赢得Snake Ladder的最低步骤

Question

给定一个蛇和梯子游戏,编写一个函数,返回最小跳跃数量,以取得顶部或目标位置.你可以假设你抛出的骰子总是有利于你

**

这是我的解决方案,但不确定它是否正确.

这个问题类似于数组中的青蛙跳跃.但在此之前,我们必须以该格式对问题进行建模.

如果没有蛇或梯子,则创建一个大小为100的数组和每个位置存储器6.店铺跳数.如果梯子出现在那一点上.如果存在蛇,则存储-ve跳转到该位置.

现在我们必须解决我们可以达到的最小步数.在O(n ^ 2)时间复杂度和O(n)空间中使用动态编程可以解决主要问题.

Answer 1

看看这篇博文,它使用蒙特卡罗模拟和马尔可夫链对滑槽和梯子进行了全面的数学分析.他确实展示了计算步骤的最小数量取胜的方式(基本构造一个转换矩阵,看看你有多少次乘以初始载体去具有非零最终位置的解决方案).这可能不是最有效的方式,但这篇文章非常值得一读.

这是python中使用sets的快速解决方案.我从博客文章中获得了跳转表中的数字.在每一步,它只是计算从上一步可以到达的所有位置,并继续这样做,直到最终位置在可到达的位置中:

jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
  98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0

while final_pos not in positions:
    nsteps += 1
    old_positions = positions
    positions = set()
    for pos in old_positions:
        for dice in range(1, 7):
            new_pos = pos + dice
            positions.add(jumps.get(new_pos, new_pos))

print 'Reached finish in %i steps' % nsteps            

执行时间可以忽略不计,它会吐出7的正确答案(见博客).