Pythonの蛇と梯子ゲームの最小の動きを見つけるためのプログラム

蛇と梯子のゲームをしているとしましょう。サイコロを振って好きな数だけ振ることができるという条件があります。位置0から開始し、目的地は位置100で、サイコロを数回転がして目的地に到達します。ボード上の蛇と梯子の位置が提供されている場合、目的地に到達するために必要なダイスロールの最小数を見つける必要があります。蛇と梯子の配列は、ボード内の蛇と梯子の位置を表し、配列には、ボード上の蛇または梯子の開始値と終了値が含まれています。

したがって、入力がラダー=[（11、40）、（37,67）、（47、73）、（15、72）]のようである場合、ヘビ=[（90、12）、（98、31）、 （85、23）、（75、42）、（70、18）、（49、47）]の場合、出力は8になります。

蛇と梯子の位置を考えると、ボード上の100番目の位置に到達するために必要な最小移動回数は8回です。

これを解決するには、次の手順に従います-

• アレイスネークをアレイラダーに追加します
• edges：=新しいマップ
• はしごの各ペアf、tについて、
  • edges [f]：=t
• u：=新しいセット
• v：=新しいセット
• vに（1）を追加
• m：=0
• vには100が存在しませんが、
  • m：=m + 1
  • w：=新しいセット
  • vのfごとに、
    • 1から6の範囲のiについては、
      • n：=f + i
      • nがエッジに存在する場合、
        • n：=エッジ[n]
      • nがuに存在する場合、
        • 次の反復に進む
      • uに（n）を追加
      • wに（n）を追加
  • v：=w
• return 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