数据结构
网络
关系型数据库管理系统 (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 次浏览
广告