数据结构
网络
关系型数据库管理系统
操作系统
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
更新日期：16-Jun-2020
1K+ 浏览
广告