14

给定一个蛇和梯子游戏，编写一个函数，返回跳到顶部或目标位置的最小次数。你可以假设你掷出的骰子总是对你有利

**

这是我的解决方案，但不确定它是否正确。

这个问题类似于数组中的青蛙跳跃。但在此之前，我们必须以这种格式对问题进行建模。

创建一个大小为 100 的数组，如果没有蛇或梯子，则为每个位置存储 6 个。存储跳转计数。如果那个时候有梯子。如果存在蛇，则在该位置存储 -ve 跳转。

现在我们必须解决直到最后我们可以达到多少个最小步骤。主要问题可以使用 O(n^2) 时间复杂度和 O(n ) 空间中的动态规划来解决。

4

7 回答 7

6

看看这篇博文，它使用蒙特卡洛模拟和马尔可夫链对滑槽和梯子进行了全面的数学分析。他确实展示了一种计算获胜的最小步数的方法（基本上是构建一个转换矩阵，看看你必须将起始向量乘以多少次才能得到最终位置非零的解）。这可能不是最有效的方法，但这篇文章非常值得一读。

这是使用集合的python快速解决方案。我从博客文章中得到了跳转表中的数字。在每一步，它只是简单地计算上一步中所有可到达的位置，并继续这样做，直到最终位置在可到达的位置中：

jumps = {1: 38, 4: 14, 9: 31, 21: 42, 28: 84, 36: 44, 51: 67, 71: 91, 80: 100,
  98: 78, 95: 75, 93: 73, 87: 24, 64: 60, 62: 19, 56: 53, 49: 11, 48: 26, 16: 6}
final_pos = 100
positions = {0} #initial position off the board
nsteps = 0

while final_pos not in positions:
    nsteps += 1
    old_positions = positions
    positions = set()
    for pos in old_positions:
        for dice in range(1, 7):
            new_pos = pos + dice
            positions.add(jumps.get(new_pos, new_pos))

print 'Reached finish in %i steps' % nsteps

执行时间可以忽略不计，它会吐出正确的答案（见博客）7。

于 2013-08-19T19:37:19.117 回答
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 在他的回答中链接到的博客文章。此代码将打印（其中一个）最短路径到板上每个可到达的方格，以：

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

该程序模拟实际场景..如果符合预期，请告诉我..

import java.util.HashMap;
import java.util.Map;

public class SnakeLadder {

    private Map<Integer,Integer> snakeLadderMapping=new HashMap<Integer,Integer>();


    private int winPosition=100;
    private int currentPosition=1;

    public SnakeLadder(){
        snakeLadderMapping.put(9, 19);
        snakeLadderMapping.put(17, 5);
        snakeLadderMapping.put(12, 40);
        snakeLadderMapping.put(24, 60);
        snakeLadderMapping.put(68, 89);
        snakeLadderMapping.put(50, 12);
        snakeLadderMapping.put(84, 98);
        snakeLadderMapping.put(75, 24);
        snakeLadderMapping.put(72, 16);
    }

    public int startGame(){
        int count=0;
        while(currentPosition!=winPosition){
            count++;
            getNextPosition(rollDice());
        }
        System.out.println("Game Won!!!!!!");
        return count;
    }

    public int rollDice(){
        return 1+ (int)(Math.random()*5);
    }

    public void getNextPosition(int diceValue){
        int temp=currentPosition+diceValue;
        if(snakeLadderMapping.containsKey(temp)){
            currentPosition=snakeLadderMapping.get(temp);
        }else{
            if(temp<=winPosition){
                currentPosition=temp;
            }
        }
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        SnakeLadder l=new SnakeLadder();
        System.out.println("No of Steps to win:"+l.startGame());

    }

}
于 2013-12-30T07:10:16.907 回答
0

广度优先搜索 (BFS) 或动态规划解决方案将使用 O(N) 空间在 O(N) 时间内工作。

初始化：保留一个辅助数组来保留梯子和蛇。假设有一个从第 x 个单元格到第 y 个单元格的梯子。所以辅助[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 回答
0

o(n) 中的 C# 中的解决方案。

建立一个帮助矩阵来检查每个步骤，看看到达那里的最小方法是什么，然后添加一个。

const int BoardSize = 100;
const int MaxStep = 6;
static void Main()
{

    // - means a ledder ending at the pos
    // + means a snake (taking you back n steps)
    int[] arr = new int[] {     
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,      8,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1,     -1, 
                            -1,     -1,     -1,     -1,     -1,     -1,     -1,     -71,    -1,     -1      };

    Console.WriteLine("Steps needed: " + solve(arr));
}

public static int solve(int[] inArr)
{
    int[] arr = new int[BoardSize];

    arr[0] = 1;

    for (int i = 0; i < BoardSize; ++i)
    {
        // steps here is the minimum of all the positions in all the previos 6 cells +1
        if (i < MaxStep)
            arr[i] = 1;
        else
        {
            int extraOption = int.MaxValue;
            if (inArr[i] < -1 || inArr[i] > 0)
                extraOption = arr[i + inArr[i]];
            else if (inArr[i] > 0)
                extraOption = arr[i + inArr[i]];
            arr[i] = min(arr[i - 1], arr[i - 2], arr[i - 3], arr[i - 4], arr[i - 5], arr[i - 6], extraOption) + 1;
        }
    }

    for (int i = 0; i < BoardSize; ++i)
    {
        Console.Write(arr[i] + "\t");
        if ((i + 1) % 10 == 0)
            Console.WriteLine("");
    }

    return arr[arr.Length-1];
}

public static int min(int a, int b, int c, int d, int e, int f, int g)
{
    int ab = Math.Min(a,b);
    int cd = Math.Min(c,d);
    int ef = Math.Min(e,f);
    return Math.Min(Math.Min(ab, cd), Math.Min(ef,g));
}
于 2013-08-21T08:00:15.880 回答
0
  1. 将每个视为有向图中的一个顶点。2.从单元格 1 中，您可以转到单元格 2、3、4、5、6、7，因此顶点 1 的边将指向顶点 2、顶点 3……。顶点 7。对于其余单元格，同样考虑这一点。
  2. 对于蛇 - 连接从蛇顶点的头部到蛇顶点的尾部的有向边。
  3. 对于梯子，从梯子顶点的底部连接有向边到梯子顶点的顶部。
    1. 现在问题被简化为短路问题。所以通过广度优先搜索（使用队列）我们可以解决这个问题。

在此处查看完整的代码解决方案 - https://algorithms.tutorialhorizo​​n.com/snake-and-ladder-problem/

于 2018-03-15T02:29:38.363 回答