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，執行以下操作：
      • 對於範圍 1 到 6 中的每個 i，執行以下操作：
        • 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

更新於：2021年10月6日

871 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告