Dado un tablero de serpientes y escaleras, encuentre el número mínimo de lanzamientos de dados necesarios para llegar al destino o la última celda desde el origen o la primera celda. Básicamente, el jugador tiene control total sobre el resultado del lanzamiento de dados y quiere averiguar el número mínimo de lanzamientos necesarios para llegar a la última celda.
Si el jugador llega a una celda que es la base de una escalera, el jugador tiene que subir esa escalera y si llega a una celda es la boca de la serpiente, y tiene que bajar a la cola de la serpiente sin tirar los dados.
Por ejemplo, considere el tablero que se muestra, el número mínimo de lanzamientos de dados necesarios para llegar a la celda 30 desde la celda 1 es 3.
Los siguientes son los pasos:
a) Primero tire dos dados para llegar a la celda número 3 y luego una escalera para llegar a 22
b) Luego tira 6 para llegar a 28.
c) Finalmente por 2 para llegar a 30.
También pueden haber otras soluciones como (2, 2, 6), (2, 4, 4), (2, 3, 5).. etc.
La idea es considerar el tablero de serpiente y escalera dado como un gráfico dirigido con un número de vértices igual al número de celdas en el tablero. El problema se reduce a encontrar el camino más corto en un gráfico. Cada vértice del gráfico tiene una arista hacia los siguientes seis vértices si los siguientes 6 vértices no tienen una serpiente o una escalera. Si alguno de los siguientes seis vértices tiene una serpiente o una escalera, entonces el borde del vértice actual va a la parte superior de la escalera o cola de la serpiente. Dado que todos los bordes tienen el mismo peso, podemos encontrar de manera eficiente la ruta más corta utilizando la búsqueda primero en amplitud del gráfico.
A continuación se muestra la implementación de la idea anterior. La entrada está representada por dos cosas, la primera es ‘N’, que es un número de celdas en el tablero dado, la segunda es una array ‘move[0…N-1]’ de tamaño N. Una entrada move[i] es -1 si no hay serpiente ni escalera desde i, de lo contrario move[i] contiene el índice de la celda de destino para la serpiente o la escalera en i.
C++
// C++ program to find minimum number of dice throws
// required to reach last cell from first cell of a given
// snake and ladder board
#include <iostream>
#include <queue>
using namespace std;
// An entry in queue used in BFS
struct queueEntry {
int v; // Vertex number
int dist; // Distance of this vertex from source
};
// This function returns minimum number of dice throws
// required to Reach last cell from 0'th cell in a snake and
// ladder game. move[] is an array of size N where N is no.
// of cells on board If there is no snake or ladder from
// cell i, then move[i] is -1 Otherwise move[i] contains
// cell to which snake or ladder at i takes to.
int getMinDiceThrows(int move[], int N)
{
// The graph has N vertices. Mark all the vertices as
// not visited
bool* visited = new bool[N];
for (int i = 0; i < N; i++)
visited[i] = false;
// Create a queue for BFS
queue<queueEntry> q;
// Mark the node 0 as visited and enqueue it.
visited[0] = true;
queueEntry s
= { 0, 0 }; // distance of 0't vertex is also 0
q.push(s); // Enqueue 0'th vertex
// Do a BFS starting from vertex at index 0
queueEntry qe; // A queue entry (qe)
while (!q.empty()) {
qe = q.front();
int v = qe.v; // vertex no. of queue entry
// If front vertex is the destination vertex,
// we are done
if (v == N - 1)
break;
// Otherwise dequeue the front vertex and enqueue
// its adjacent vertices (or cell numbers reachable
// through a dice throw)
q.pop();
for (int j = v + 1; j <= (v + 6) && j < N; ++j) {
// If this cell is already visited, then ignore
if (!visited[j]) {
// Otherwise calculate its distance and mark
// it as visited
queueEntry a;
a.dist = (qe.dist + 1);
visited[j] = true;
// Check if there a snake or ladder at 'j'
// then tail of snake or top of ladder
// become the adjacent of 'i'
if (move[j] != -1)
a.v = move[j];
else
a.v = j;
q.push(a);
}
}
}
// We reach here when 'qe' has last vertex
// return the distance of vertex in 'qe'
return qe.dist;
}
// Driver program to test methods of graph class
int main()
{
// Let us construct the board given in above diagram
int N = 30;
int moves[N];
for (int i = 0; i < N; i++)
moves[i] = -1;
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
cout << "Min Dice throws required is "
<< getMinDiceThrows(moves, N);
return 0;
}
Java
// Java program to find minimum number of dice
// throws required to reach last cell from first
// cell of a given snake and ladder board
import java.util.LinkedList;
import java.util.Queue;
public class SnakesLadder {
// An entry in queue used in BFS
static class qentry {
int v; // Vertex number
int dist; // Distance of this vertex from source
}
// This function returns minimum number of dice
// throws required to Reach last cell from 0'th cell
// in a snake and ladder game. move[] is an array of
// size N where N is no. of cells on board If there
// is no snake or ladder from cell i, then move[i]
// is -1 Otherwise move[i] contains cell to which
// snake or ladder at i takes to.
static int getMinDiceThrows(int move[], int n)
{
int visited[] = new int[n];
Queue<qentry> q = new LinkedList<>();
qentry qe = new qentry();
qe.v = 0;
qe.dist = 0;
// Mark the node 0 as visited and enqueue it.
visited[0] = 1;
q.add(qe);
// Do a BFS starting from vertex at index 0
while (!q.isEmpty()) {
qe = q.remove();
int v = qe.v;
// If front vertex is the destination
// vertex, we are done
if (v == n - 1)
break;
// Otherwise dequeue the front vertex and
// enqueue its adjacent vertices (or cell
// numbers reachable through a dice throw)
for (int j = v + 1; j <= (v + 6) && j < n;
++j) {
// If this cell is already visited, then
// ignore
if (visited[j] == 0) {
// Otherwise calculate its distance and
// mark it as visited
qentry a = new qentry();
a.dist = (qe.dist + 1);
visited[j] = 1;
// Check if there a snake or ladder at
// 'j' then tail of snake or top of
// ladder become the adjacent of 'i'
if (move[j] != -1)
a.v = move[j];
else
a.v = j;
q.add(a);
}
}
}
// We reach here when 'qe' has last vertex
// return the distance of vertex in 'qe'
return qe.dist;
}
public static void main(String[] args)
{
// Let us construct the board given in above diagram
int N = 30;
int moves[] = new int[N];
for (int i = 0; i < N; i++)
moves[i] = -1;
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
System.out.println("Min Dice throws required is "
+ getMinDiceThrows(moves, N));
}
}
Python3
# Python3 program to find minimum number
# of dice throws required to reach last
# cell from first cell of a given
# snake and ladder board
# An entry in queue used in BFS
class QueueEntry(object):
def __init__(self, v=0, dist=0):
self.v = v
self.dist = dist
'''This function returns minimum number of
dice throws required to. Reach last cell
from 0'th cell in a snake and ladder game.
move[] is an array of size N where N is
no. of cells on board. If there is no
snake or ladder from cell i, then move[i]
is -1. Otherwise move[i] contains cell to
which snake or ladder at i takes to.'''
def getMinDiceThrows(move, N):
# The graph has N vertices. Mark all
# the vertices as not visited
visited = [False] * N
# Create a queue for BFS
queue = []
# Mark the node 0 as visited and enqueue it
visited[0] = True
# Distance of 0't vertex is also 0
# Enqueue 0'th vertex
queue.append(QueueEntry(0, 0))
# Do a BFS starting from vertex at index 0
qe = QueueEntry() # A queue entry (qe)
while queue:
qe = queue.pop(0)
v = qe.v # Vertex no. of queue entry
# If front vertex is the destination
# vertex, we are done
if v == N - 1:
break
# Otherwise dequeue the front vertex
# and enqueue its adjacent vertices
# (or cell numbers reachable through
# a dice throw)
j = v + 1
while j <= v + 6 and j < N:
# If this cell is already visited,
# then ignore
if visited[j] is False:
# Otherwise calculate its
# distance and mark it
# as visited
a = QueueEntry()
a.dist = qe.dist + 1
visited[j] = True
# Check if there a snake or ladder
# at 'j' then tail of snake or top
# of ladder become the adjacent of 'i'
a.v = move[j] if move[j] != -1 else j
queue.append(a)
j += 1
# We reach here when 'qe' has last vertex
# return the distance of vertex in 'qe
return qe.dist
# driver code
N = 30
moves = [-1] * N
# Ladders
moves[2] = 21
moves[4] = 7
moves[10] = 25
moves[19] = 28
# Snakes
moves[26] = 0
moves[20] = 8
moves[16] = 3
moves[18] = 6
print("Min Dice throws required is {0}".
format(getMinDiceThrows(moves, N)))
# This code is contributed by Ajitesh Pathak
C#
// C# program to find minimum
// number of dice throws required
// to reach last cell from first
// cell of a given snake and ladder board
using System;
using System.Collections.Generic;
public class SnakesLadder {
// An entry in queue used in BFS
public class qentry {
public int v; // Vertex number
public int
dist; // Distance of this vertex from source
}
// This function returns minimum number of dice
// throws required to Reach last cell from 0'th cell
// in a snake and ladder game. move[] is an array of
// size N where N is no. of cells on board If there
// is no snake or ladder from cell i, then move[i]
// is -1 Otherwise move[i] contains cell to which
// snake or ladder at i takes to.
static int getMinDiceThrows(int[] move, int n)
{
int[] visited = new int[n];
Queue<qentry> q = new Queue<qentry>();
qentry qe = new qentry();
qe.v = 0;
qe.dist = 0;
// Mark the node 0 as visited and enqueue it.
visited[0] = 1;
q.Enqueue(qe);
// Do a BFS starting from vertex at index 0
while (q.Count != 0) {
qe = q.Dequeue();
int v = qe.v;
// If front vertex is the destination
// vertex, we are done
if (v == n - 1)
break;
// Otherwise dequeue the front vertex and
// enqueue its adjacent vertices (or cell
// numbers reachable through a dice throw)
for (int j = v + 1; j <= (v + 6) && j < n;
++j) {
// If this cell is already visited, then
// ignore
if (visited[j] == 0) {
// Otherwise calculate its distance and
// mark it as visited
qentry a = new qentry();
a.dist = (qe.dist + 1);
visited[j] = 1;
// Check if there a snake or ladder at
// 'j' then tail of snake or top of
// ladder become the adjacent of 'i'
if (move[j] != -1)
a.v = move[j];
else
a.v = j;
q.Enqueue(a);
}
}
}
// We reach here when 'qe' has last vertex
// return the distance of vertex in 'qe'
return qe.dist;
}
// Driver code
public static void Main(String[] args)
{
// Let us construct the board
// given in above diagram
int N = 30;
int[] moves = new int[N];
for (int i = 0; i < N; i++)
moves[i] = -1;
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
Console.WriteLine("Min Dice throws required is "
+ getMinDiceThrows(moves, N));
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find minimum number of dice
// throws required to reach last cell from first
// cell of a given snake and ladder board
class qentry
{
constructor()
{
this.v = 0;
this.dist = 0;
}
}
// This function returns minimum number of dice
// throws required to Reach last cell from 0'th cell
// in a snake and ladder game. move[] is an array of
// size N where N is no. of cells on board If there
// is no snake or ladder from cell i, then move[i]
// is -1 Otherwise move[i] contains cell to which
// snake or ladder at i takes to.
function getMinDiceThrows(move,n)
{
let visited = new Array(n);
for(let i = 0; i < n; i++)
visited[i] = false;
let q = [];
let qe = new qentry();
qe.v = 0;
qe.dist = 0;
// Mark the node 0 as visited and enqueue it.
visited[0] = 1;
q.push(qe);
// Do a BFS starting from vertex at index 0
while (q.length != 0)
{
qe = q.shift();
let v = qe.v;
// If front vertex is the destination
// vertex, we are done
if (v == n - 1)
break;
// Otherwise dequeue the front vertex and
// enqueue its adjacent vertices (or cell
// numbers reachable through a dice throw)
for (let j = v + 1; j <= (v + 6) && j < n; ++j)
{
// If this cell is already visited, then ignore
if (visited[j] == 0)
{
// Otherwise calculate its distance and
// mark it as visited
let a = new qentry();
a.dist = (qe.dist + 1);
visited[j] = 1;
// Check if there a snake or ladder at 'j'
// then tail of snake or top of ladder
// become the adjacent of 'i'
if (move[j] != -1)
a.v = move[j];
else
a.v = j;
q.push(a);
}
}
}
// We reach here when 'qe' has last vertex
// return the distance of vertex in 'qe'
return qe.dist;
}
// Let us construct the board given in above diagram
let N = 30;
let moves = new Array(N);
for (let i = 0; i < N; i++)
moves[i] = -1;
// Ladders
moves[2] = 21;
moves[4] = 7;
moves[10] = 25;
moves[19] = 28;
// Snakes
moves[26] = 0;
moves[20] = 8;
moves[16] = 3;
moves[18] = 6;
document.write("Min Dice throws required is " +
getMinDiceThrows(moves, N));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Min Dice throws required is 3
La complejidad de tiempo de la solución anterior es O (N) ya que cada celda se agrega y elimina solo una vez de la cola. Y una operación típica de encolado o desencolado toma O(1) tiempo.
Otro enfoque que podemos pensar es la recursión en la que iremos a cada bloque, en este caso, que es del 1 al 30, y llevaremos la cuenta de un número mínimo de lanzamientos de dados en el bloque i y lo almacenaremos en una array. t.
Entonces, básicamente, haremos lo siguiente:
- Cree una array, digamos ‘t’, e inicialícela con -1.
- Ahora llamaremos a una función recursiva del bloque 1, con una variable, digamos ‘i’, y la incrementaremos.
- En esto, definiremos la condición base, ya que siempre que el número de bloque alcance 30 o más, devolveremos 0 y también verificaremos si este bloque ha sido visitado antes, esto lo haremos verificando el valor de t[i], si este es -1 entonces significa que no se ha visitado y avanzamos con la función sino se ha visitado y devolveremos el valor de t[i].
- Después de verificar los casos base, inicializaremos una variable ‘min’ con un valor entero máximo.
- Ahora iniciaremos un bucle de 1 a 6, es decir, los valores de un dado, ahora para cada iteración aumentaremos el valor de i por el valor de dados (por ejemplo: i+1,i+2….i+6) y verificaremos si algún valor aumentado tiene una escalera, si la hay, actualizaremos el valor de i al final de la escalera y luego pasaremos el valor a la función recursiva, si no hay una escalera, también pasaremos el valor incrementado de i basado en el valor de los dados a una función recursiva, pero si hay una serpiente entonces no pasaremos este valor a la función recursiva ya que queremos llegar al final lo antes posible, y lo mejor de hacer esto sería ser no ser mordido por una serpiente. Y seguiríamos actualizando el valor mínimo para la variable ‘min’.
- Finalmente actualizaremos t[i] con min y devolveremos t[i].
A continuación se muestra la implementación del enfoque anterior:
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Initialise an array t of length 31, we will use from
// index to 1 to 30
static int[] t = new int[31];
static int minThrow(int n, int arr[])
{
// code here
for (int i = 0; i < 31; i++) {
// initialising every index of t with -1
t[i] = -1;
}
// create hashmap to store snakes and ladders start
// and end for better efficiency
HashMap<Integer, Integer> h = new HashMap<>();
for (int i = 0; i < 2 * n; i = i + 2) {
// store start as key and end as value
h.put(arr[i], arr[i + 1]);
}
// final ans
return sol(1, h);
}
// recursive function
static int sol(int i, HashMap<Integer, Integer> h)
{
// base condintion
if (i >= 30)
return 0;
// checking if block is already visited or
// not(memoization).
else if (t[i] != -1)
return t[i];
// initialising min as max int value
int min = Integer.MAX_VALUE;
// for loop for every dice value from 1 to 6
for (int j = 1; j <= 6; j++) {
// incrementing value of i with dice value i.e j
// taking new variable k
//->taking new variable so that we dont change i
// as we will need it again in another iteration
int k = i + j;
if (h.containsKey(k)) {
// checking if this is a snake of ladder
// if a snake then we continue as we dont
// need a snake
if (h.get(k) < k)
continue;
// updating if its a ladder to ladder end
// value
k = h.get(k);
}
// updating min in every iteration for getting
// minimum throws from this particular block
min = Math.min(min, sol(k, h) + 1);
}
// updating value of t[i] to min
// memoization
t[i] = min;
return t[i];
}
// main
public static void main(String[] args)
{
// Given a 5x6 snakes and ladders board
// You are given an integer N denoting the total
// number of snakes and ladders and an array arr[]
// of 2*N size where 2*i and (2*i + 1)th values
// denote the starting and ending point respectively
// of ith snake or ladder
int N = 8;
int[] arr = new int[2 * N];
arr[0] = 3;
arr[1] = 22;
arr[2] = 5;
arr[3] = 8;
arr[4] = 11;
arr[5] = 26;
arr[6] = 20;
arr[7] = 29;
arr[8] = 17;
arr[9] = 4;
arr[10] = 19;
arr[11] = 7;
arr[12] = 27;
arr[13] = 1;
arr[14] = 29;
arr[15] = 9;
System.out.println("Min Dice throws required is "
+ minThrow(N, arr));
}
}
Producción
Min Dice throws required is 3
Complejidad temporal: O(N).
Espacio Auxiliar O(N)
Este artículo es una contribución de Siddharth y Sahil Srivastava . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA