Bài toán Rắn và Thang (Snake and Ladder Problem)

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

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

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

Đầu vào: Vị trí bắt đầu và kết thúc của rắn và thang.
Rắn: Từ 26 đến 0, Từ 20 đến 8, Từ 16 đến 3, Từ 18 đến 6
Thang: Từ 2 đến 21, Từ 4 đến 7, Từ 10 đến 25, Từ 19 đến 28
Đầu ra: Số lần tung xúc xắc tối thiểu là 3

Thuật toán

minDiceThrow(move, cell)
Đầu vào: Vị trí nhảy cho rắn hoặc thang, và tổng số ô.
Đầu ra: Số lần tung xúc xắc tối thiểu để đến ô cuối cùng.
Bắt đầu
  ban đầu đánh dấu tất cả ô là chưa thăm
  định nghĩa hàng đợi q
  đánh dấu đỉnh bắt đầu là đã thăm
  cho đỉnh bắt đầu: số đỉnh := 0 và khoảng cách := 0
  thêm đỉnh bắt đầu s vào q
  trong khi q không rỗng, thực hiện
    qVert := phần tử đầu hàng đợi
    v := số đỉnh của qVert
    nếu v = cell - 1 thì // khi là đỉnh cuối
      thoát vòng lặp
    xóa một mục khỏi hàng đợi
    với j := v + 1, đến v + 6 và j < cell, tăng j lên 1, thực hiện
      nếu j chưa được thăm thì
        newVert.dist := (qVert.dist + 1)
        đánh dấu v là đã thăm
        nếu có rắn hoặc thang thì
          newVert.vert := move[j] // nhảy đến vị trí đó
        ngược lại
          newVert.vert := j
        chèn newVert vào hàng đợi
      kết thúc
    kết thúc
  kết thúc
  trả về qVert.dist
Kết thúc

Ví dụ (C++)

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

struct vertex {
  int vert;
  int dist; // Khoảng cách của đỉnh này từ nguồn
};

int minDiceThrow(int move[], int cell) {
  bool visited[cell];
  for (int i = 0; i < cell; i++)
    visited[i] = false; // ban đầu tất cả ô chưa thăm
  
  queue<vertex> q;
  visited[0] = true; // ban đầu bắt đầu từ 0
  vertex s = {0, 0};
  q.push(s); // Enqueue đỉnh 0
  
  vertex qVert;
  while (!q.empty()) {
    qVert = q.front();
    int v = qVert.vert;
    if (v == cell-1) // khi v là đỉnh đích
      break;
    q.pop();
    for (int j = v+1; j <= (v+6) && j < cell; ++j) {
      // cho 1 đến 6 ô tiếp theo
      if (!visited[j]) {
        vertex newVert;
        newVert.dist = (qVert.dist + 1); // ban đầu khoảng cách tăng 1
        visited[j] = true;
        if (move[j] != -1)
          newVert.vert = move[j]; // nếu ô j có rắn hoặc thang
        else
          newVert.vert = j;
        q.push(newVert);
      }
    }
  }
  return qVert.dist; // số lần tung xúc xắc tối thiểu
}

int main() {
  int cell = 30; // coi như có 30 ô
  int moves[cell];
  for (int i = 0; i < cell; i++)
    moves[i] = -1; // ban đầu không khởi tạo rắn hoặc thang
  
  // Với thang ở ô i, nó nhảy đến move[i]
  moves[2] = 21;
  moves[4] = 7;
  moves[10] = 25;
  moves[19] = 28;
  
  // Với rắn ở ô i, nó nhảy đến 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