뱀과 사다리 문제

저희는 유명한 게임인 뱀과 사다리에 대해 알고 있습니다. 이 게임에서 일부 방은 방 번호와 함께 보드에 있습니다. 일부 객실은 사다리 또는 뱀으로 연결되어 있습니다. 사다리를 얻으면 어떤 방까지 올라갈 수 있어 순차적으로 움직이지 않고 목적지에 가까워질 수 있다. 마찬가지로, 뱀을 잡으면 더 낮은 방으로 보내어 그 방에서 다시 여행을 시작합니다.

이 문제에서는 시작점에서 목적지까지 도달하는 데 필요한 최소 주사위 수를 찾아야 합니다.

입력 및 출력

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