ปัญหาปีนบันไดและลื่นงู (Snake and Ladder Problem)

เกมงูและบันได (Snake and Ladder) มีห้องต่างๆ บนกระดาน บางห้องเชื่อมด้วยบันได (เลื่อนขึ้น) บางห้องเชื่อมด้วยงู (ลื่นลง) ต้องการหาจำนวนครั้งทอยลูกเต๋าน้อยที่สุดเพื่อไปจากจุดเริ่มต้นถึงจุดหมาย

การรับค่าและแสดงผล

Input: ตำแหน่งงูและบันได
Snake: 26→0, 20→8, 16→3, 18→6
Ladder: 2→21, 4→7, 10→25, 19→28

Output: Min Dice throws required is 3

อัลกอริทึม

minDiceThrow(move, cell) - ใช้ BFS หาเส้นทางสั้นที่สุด

Begin
  ทำเครื่องหมายทุกห้องว่าไม่ได้เยี่ยมชม
  กำหนดคิว q
  ทำเครื่องหมายห้องเริ่มต้น (0) ว่าเยี่ยมชมแล้ว ระยะทาง = 0
  เพิ่มห้องเริ่มต้นเข้า q
  
  while q ไม่ว่าง do
    qVert := หน้าคิว
    v := หมายเลขห้องของ qVert
    
    if v = cell - 1 then break  // ถึงจุดหมาย
    
    ลบหน้าคิวออก
    
    for j := v+1 ถึง v+6 และ j < cell do
      if j ไม่ได้เยี่ยมชม then
        newVert.dist := qVert.dist + 1
        ทำเครื่องหมาย j ว่าเยี่ยมชมแล้ว
        
        if มีงูหรือบันไดที่ j then
          newVert.vert := move[j]  // กระโดดไปตำแหน่งใหม่
        else
          newVert.vert := j
        end if
        
        เพิ่ม newVert เข้า q
      end if
    done
  done
  
  return qVert.dist
End

ตัวอย่างโค้ด (C++)

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

struct vertex { int vert, dist; };

int minDiceThrow(int move[], int cell) {
  bool visited[cell];
  for(int i = 0; i < cell; i++) visited[i] = false;
  
  queue<vertex> q;
  visited[0] = true;
  vertex s = {0, 0};
  q.push(s);
  
  vertex qVert;
  while(!q.empty()) {
    qVert = q.front();
    int v = qVert.vert;
    if(v == cell-1) break;
    q.pop();
    
    for(int j = v+1; j <= v+6 && j < cell; ++j) {
      if(!visited[j]) {
        vertex newVert;
        newVert.dist = qVert.dist + 1;
        visited[j] = true;
        if(move[j] != -1) newVert.vert = move[j];
        else newVert.vert = j;
        q.push(newVert);
      }
    }
  }
  return qVert.dist;
}

int main() {
  int cell = 30;
  int moves[cell];
  for(int i = 0; i < cell; i++) moves[i] = -1;
  
  // Ladder
  moves[2] = 21; moves[4] = 7; moves[10] = 25; moves[19] = 28;
  // Snake
  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