14

ヘビとはしごのゲームが与えられた場合、トップまたは目的の位置を取るためのジャンプの最小回数を返す関数を作成します。あなたが投げたサイコロは常にあなたに有利な結果をもたらすと仮定することができます

**

これが私の解決策ですが、それが正しいかどうかはわかりません。

この問題は、配列内のフロッグ ジャンプに似ていますが、その前に、その形式で問題をモデル化する必要があります。

サイズ 100 の配列を作成し、蛇やはしごがない場合は位置ごとに 6 を格納します。ストアジャンプカウント。はしごがその時点で存在する場合。スネークが存在する場合は、その場所に -ve jump を保存します。

次に、最後まで到達できる最小ステップ数を解決する必要があります。主な問題は、O(n^2) 時間の複雑さと O(n ) 空間で動的計画法を使用して解決できます。

4

7 に答える 7

3

Python での単純な幅優先検索ソリューションを次に示します。

# the target square and the positions of the snakes and ladders:
top = 100
jump = { 1: 38,  4: 14,  9: 31, 16:  6, 21: 42, 28: 84, 36: 44,
        48: 26, 49: 11, 51: 67, 56: 53, 62: 19, 64: 60, 71: 91,
        80:100, 87: 24, 93: 73, 95: 75, 98: 78}

# start from square 0 (= outside the board) after 0 rolls
open = {0}
path = {0: ()}

while len(open) > 0:
    i = open.pop()
    p = path[i] + (i,)
    for j in xrange(i+1, i+7):
        if j > top: break
        if j in jump: j = jump[j]
        if j not in path or len(path[j]) > len(p):
            open.add(j)
            path[j] = p

for i in path:
    print "Square", i, "can be reached in", len(path[i]), "rolls via", path[i]

ボード レイアウト (つまり、jump辞書) は、Bas Swinckels の回答でリンクされているブログ投稿から取得されます。このコードは、ボード上の到達可能な各正方形への最短経路 (の 1 つ) を出力し、次のように終了します。

Square 100 can be reached in 7 rolls via (0, 38, 41, 45, 67, 68, 74)

完全な出力が必要な場合は、ideone.com でこのデモを参照してください。

于 2013-08-19T20:49:16.470 に答える
1

これをC#で実装しました。ここで私の要点を確認できます。以下にコードも貼り付けておきます。

私の実装では、次のことを考慮しました。

  • ループの回避: これは、ヘビがはしごを横切るときに発生します。たとえば、はしごの端が蛇の頭で、蛇の尻尾が同じはしごの始点である場合などです。これは単純な例ですが、もっと複雑なループがあるかもしれません。
  • 良いヘビを取る: すべてのヘビを避ける必要はないことに気付きました. ターゲットにすばやく到達するのに役立つため、ヘビを取る必要がある場合があります。私はそれらを「良いヘビ」と呼んでいます。たとえば、3>60 の次に61>50 の次に 51>100 (ターゲット)。ヘビを取る場合、最小ダイス数は 3 で、ヘビなしでは 8 になります。
  • オプションのジャンプと必須のジャンプ: オプションのジャンプが false に設定されている場合、アルゴリズムは 1 つになったときにジャンプする必要があります。

  • 最短経路の認識: アルゴリズムがターゲットに到達すると、最短経路が登録され、計算中に現在見つかったソリューションよりも長い検索が破棄されます。これにより、複雑な状況でのプロセスが大幅に高速化されます。

    using System;
using System.Collections.Generic;
using System.Linq;
namespace SnakeAndLaddersSolution
{
  public class SnakeAndLadder
  {
    private struct Jump
   {
     public int Start;
     public int End;
   }

   private const int TOP = 100;
   private const int STEP_SIZE = 6;
   private int _minDiceCount = int.MaxValue;
   private readonly List<Jump> _jumps = new List<Jump>();

   public bool OptionalJump { get; set; }

   public void AddJump(int start, int end)
   {
       _jumps.Add(new Jump { Start = start, End = end });
   }

   public int Solve()
   {
       var path = new Stack<int>();
       path.Push(1); //start from square 1
       return FindMinimumDice(path, 0);
   }

   private int FindMinimumDice(Stack<int> path, int diceCount)
   {
       if (diceCount >= _minDiceCount)
       {
           //too long. we've already found a shortest path.
           //drop going deeper
           return -1;
       }
       var currentSquare = path.Peek();
       var diceCounts = new List<int>();
       int newDiceCount;

       var ignoreNormalJump = false;

    for (var i = 0; i <= STEP_SIZE; i++)
    {
        var newSquare = currentSquare + i;
        if (newSquare == TOP)
        {
            //got there
            var totalDiceCount = diceCount + (i == 0 ? 0 : 1);
            _minDiceCount = Math.Min(_minDiceCount, totalDiceCount); //register the shortest path
            return totalDiceCount;
        }


        if (_jumps.All(j => j.Start != newSquare)) continue; //only process jumps

        var jump = _jumps.First(j => j.Start == newSquare);
        if (path.Contains(jump.End))
            continue; //already been here
        path.Push(jump.Start);
        path.Push(jump.End);
        newDiceCount = FindMinimumDice(path, diceCount + (i == 0 ? 0 : 1));
        path.Pop();
        path.Pop();
        if (newDiceCount != -1)
            diceCounts.Add(newDiceCount);
        if (i == 0 && !OptionalJump) //the current squre is a jump that should be taken
        {
            ignoreNormalJump = true;
            break;
        }
    }
    if (!ignoreNormalJump)
    {
        var longestJump = 0;
        for (var i = STEP_SIZE; i > 0; i--)
        {
            if (_jumps.All(j => j.Start != currentSquare + i))
            {
                longestJump = currentSquare + i;
                break;
            }
        }
        if (longestJump != 0)
        {
            path.Push(longestJump);
            newDiceCount = FindMinimumDice(path, diceCount + 1);
            path.Pop();
            if (newDiceCount != -1)
                diceCounts.Add(newDiceCount);
        }
    }
    return !diceCounts.Any() ? -1 : diceCounts.Min();
   }
  }

  class Program
  {

   static void Main(string[] args)
   {
       var sal = new SnakeAndLadder();
       //set OptionalJump to true if the jump is optional
       //sal.OptionalJump = true;
       sal.AddJump(10,60);
       sal.AddJump(51,100);
       Console.WriteLine(sal.Solve());
       Console.ReadLine();
   }
  }
  }
于 2015-06-27T03:19:24.060 に答える
0

幅優先探索 (BFS) または動的計画法のソリューションは、O(N) 空間を使用して O(N) 時間で機能します。

初期化: はしごと蛇を保持するための補助配列を保持します。x 番目のセルから y 番目のセルへのはしごがあるとします。したがって、auxi[x] = y です。セル x から y にヘビがいる場合は、x>yそのままにしておきauxi[x]=-1ます。現在のセルにはしごや蛇がない場合は、auxi[x] = x; のままにしておきます。

動的計画法のソリューション:

res[top]=0;
for(int i  = top-1; i>=0; i--) {

    res[i] = INF;
    for(int j=1; j<=6; j++){

        if(i-j<0)break;

        if(auxi[i+j]>-1)     // if i+jth cell is start of a snake, we'll always skip it
        res[i]=min( res[i] , res[auxi[i+j]]+1 );
    }

}

ヘビが始まるセルは常にスキップします。x セルでヘビが始まり、y 番目のセルで終わると仮定しましょう。ここで、y

于 2013-08-19T16:47:08.990 に答える