蛇梯问题

2023-06-21 06:32:03 183

我们知道著名的游戏蛇和梯子。在这个游戏中，一些房间出现在板上，并带有房间号。部分房间与梯子或蛇相连。当我们拿到梯子时，我们可以爬上一些房间到达目的地附近，而无需依次移动。同样，当我们得到一些蛇时，它会把我们送到一个较低的房间，从那个房间再次开始旅程。

在这个问题中，我们必须找到到达起点到终点所需的最小掷骰子数。

输入和输出

Input:
The starting and ending location of the snake and ladders.
Snake: From 26 to 0, From 20 to 8, From 16 to 3, From 18 to 6
Ladder From 2 to 21, From 4 to 7, From 10 to 25, from 19 to 28
Output:
所需的最小掷骰子是 3

算法

minDiceThrow(move, cell)

输入：蛇或梯子的跳跃位置，以及单元格的总数。
输出：到达最后一个单元格所需的最小掷骰子数。

Begin
   initially mark all cell as unvisited
   define queue q
   mark the staring vertex as visited

   for starting vertex the vertex number := 0 and distance := 0
   add starting vertex s into q
   while q is not empty, do
      qVert := front element of the queue
      v := vertex number of qVert
      if v = cell -1, then //当它是最后一个顶点时
         break the loop
      delete one item from queue
      for j := v + 1, to v + 6 and j < cell, increase j by 1, do
         if j is not visited, then
           newVert.dist:= (qVert.dist + 1)
            mark v as visited
         if there is snake or ladder, then
           newVert.vert:= move[j] //跳到那个位置
         else
           newVert.vert:= j
         insert newVert into queue
      done
   done
   return qVert.dist
End

示例

#include
#include 
using namespace std;

struct vertex {
   int vert;
   int dist;       //此顶点与源的距离
};

int minDiceThrow(int move[], int cell) {
   bool visited[cell];
   for (int i = 0; i < cell; i++)
      visited[i] = false;    //最初所有单元格都未被访问

   queue q;

   visited[0] = true;       //最初从0开始
   vertex s = {0, 0};
   q.push(s);             //将第0个顶点入队

   vertex qVert;
   while (!q.empty()) {
      qVert = q.front();
      int v = qVert.vert;

      if (v == cell-1)    //当v是目标顶点时
         break;

      q.pop();
      for (int j=v+1; j<=(v+6) && j输出结果所需的最小掷骰子是 3

蛇梯问题

输入和输出

算法

示例

热门推荐

随机推荐