Python 程序：找到“蛇和梯子”游戏中的最小步数

假设我们正在玩“蛇和梯子”游戏。我们有一个条件，可以在骰子上掷出任何我们想要的数字。我们从 0 位置开始，目标位置是 100，我们掷骰子多次以到达目的地。如果在棋盘上提供了蛇和梯子位置，则必须找出到达目标所需的最少掷骰子次数。数组“snakes”和“ladders”表示棋盘上蛇和梯子的位置，每个数组中的每个条目包含蛇或梯子的起始值和结束值。

因此，如果输入为 ladders = [(11, 40), (37,67),(47, 73),(15, 72)], snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]，则输出将为 8。

在给出蛇和梯子位置的情况下到达第 100 个位置所需的最小步数为 8。

要解决此问题，请按照以下步骤进行 –

• 将数组 snakes 添加到数组 ladders 中
• edges：一个新图
• 对于 ladders 中的每对 f，t，做以下操作:
  • edges[f] := t
• u：一个新集合
• v：一个新集合
• 将 1 添加到 v 中
• m：0
• 当 100 不在 v 中时，执行以下操作：
  • m := m + 1
  • w：一个新集合
  • 对于集合 v 中的每个 f，执行以下操作：
    • 对于 i 在 1 到 6 之间循环，执行以下操作：
    • n := f + i
    • 如果 n 在 edges 中，则
      • n := edges[n]
    • 如果 n 在 u 中，则
      • 继续下一次循环
    • 将 n 添加到 u 中
    • 将 n 添加到 w 中
  • v := w
• 返回 m

示例

以下是实现示例，以更好地理解 –

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f,t in ladders:
        edges[f] = t
    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1,7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m
print(solve([(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

输入

[(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

输出

8