蛇と梯子の問題

この問題では、開始から目的地に到達するために必要なサイコロの投げの最小数を見つける必要があります。

入力と出力

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:
Min Dice throws required is 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 //when it is last vertex
         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] //jump to that location
         else
            newVert.vert := j
         insert newVert into queue
      done
   done
   return qVert.dist
End

例

#include<iostream>
#include <queue>
using namespace std;

struct vertex {
   int vert;
   int dist;       // Distance of this vertex from source
};

int minDiceThrow(int move[], int cell) {
   bool visited[cell];
   for (int i = 0; i < cell; i++)
      visited[i] = false;    //initially all cells are unvisited

   queue<vertex> q;

   visited[0] = true;       //initially starting from 0
   vertex s = {0, 0};
   q.push(s);             // Enqueue 0'th vertex

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

      if (v == cell-1)    //when v is the destination vertex
         break;

      q.pop();
      for (int j=v+1; j<=(v+6) && j<cell; ++j) {    //for next 1 to 6 cells
         if (!visited[j]) {
            vertex newVert;
            newVert.dist = (qVert.dist + 1);       //initially distance increased by 1
            visited[j] = true;

            if (move[j] != -1)
               newVert.vert = move[j];       //if jth place have snake or ladder
            else
               newVert.vert = j;
            q.push(newVert);
         }
      }
   }
   return qVert.dist;     //number of minimum dice throw
}

int main() {
   int cell = 30;       //consider there are 30 cells
   int moves[cell];

   for (int i = 0; i<cell; i++)
      moves[i] = -1;          //initially no snake or ladder are initialized

   //For ladder in cell i, it jumps to move[i]
   moves[2] = 21;
   moves[4] = 7;
   moves[10] = 25;
   moves[19] = 28;

   //For snake in cell i, it jumps to move[i]
   moves[26] = 0;
   moves[20] = 8;
   moves[16] = 3;
   moves[18] = 6;

   cout << "Min Dice throws required is " << minDiceThrow(moves, cell);
}

出力

Min Dice throws required is 3