資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 中
- 對於範圍 1 到 6 中的每個 i，執行以下操作：
- 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 次瀏覽
廣告