資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時裝學
法律蛇梯棋問題
我們知道著名的遊戲蛇梯棋。在這個遊戲中，棋盤上存在一些房間，有房間編號。一些房間透過梯子或蛇相連。當我們遇到梯子時，我們可以爬上一些房間，無需按順序移動就可以到達目的地附近。類似地，當我們遇到蛇時，它會將我們送到較低的房間，從該房間重新開始旅程。
在這個問題中，我們必須找到從起點到達終點的最小擲骰子次數。
輸入和輸出
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
更新時間： 2020 年 6 月 16 日
1K+ 瀏覽
廣告