सांप और सीढ़ी की समस्या

हम प्रसिद्ध खेल सांप और सीढ़ी के बारे में जानते हैं। इस गेम में कुछ कमरे बोर्ड पर मौजूद होते हैं, जिसमें रूम नंबर होता है। कुछ कमरे सीढ़ी या सांप से जुड़े हुए हैं। जब हमें सीढ़ी मिल जाती है, तो हम कुछ कमरों तक चढ़ सकते हैं और बिना क्रम में आगे बढ़े गंतव्य के करीब पहुंच सकते हैं। इसी तरह, जब हमें कोई सांप मिलता है, तो वह हमें उस कमरे से फिर से यात्रा शुरू करने के लिए निचले कमरे में भेजता है।

इस समस्या में, हमें आरंभ से गंतव्य तक पहुंचने के लिए आवश्यक पासा फेंकने की न्यूनतम संख्या ज्ञात करनी होगी।

इनपुट और आउटपुट

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