Vấn đề con rắn và bậc thang

Chúng ta biết về trò chơi nổi tiếng Snake and Ladder. Trong trò chơi này, một số phòng có mặt trên bảng, với số phòng. Một số phòng được kết nối bằng thang hoặc bằng rắn. Khi có thang, chúng ta có thể leo lên một số phòng để đến gần đích mà không cần di chuyển tuần tự. Tương tự, khi chúng ta kiếm được một con rắn nào đó, nó sẽ đưa chúng ta đến một căn phòng thấp hơn để bắt đầu lại cuộc hành trình từ căn phòng đó.

Trong bài toán này, chúng ta phải tìm ra số lần ném xúc xắc tối thiểu cần thiết để đến điểm xuất phát.

Đầu vào và Đầu ra

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

Thuật toán

minDiceThrow(move, cell)

Đầu vào: vị trí nhảy cho con rắn hoặc bậc thang và tổng số ô.
Đầu ra: Số lần ném xúc xắc tối thiểu cần thiết để đến ô cuối cùng.

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

Ví dụ

#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);
}

Đầu ra

Min Dice throws required is 3