Рубрики

Проблема змеи и лестницы

Графы

Если у вас есть доска со змеями и лестницами, найдите минимальное количество бросков кубиков, необходимое для достижения пункта назначения или последней ячейки из источника или 1-й ячейки. По сути, игрок полностью контролирует результат броска костей и хочет определить минимальное количество бросков, необходимое для достижения последней клетки.

Если игрок достигает ячейки, которая является основанием лестницы, игрок должен подняться вверх по этой лестнице, и, если он достигает ячейки, являющейся пастью змеи, он должен опуститься на хвост змеи без броска кубиков.

Например, рассмотрим показанную доску, минимальное количество бросков игральных костей, необходимое для достижения ячейки 30 из ячейки 1, равно 3.
Ниже приведены шаги:

а) Сначала бросьте два кубика, чтобы добраться до клетки № 3, а затем по лестнице, чтобы достичь 22
б) Затем бросьте 6, чтобы достичь 28.
в) Наконец через 2 до 30.

Могут быть и другие решения, такие как (2, 2, 6), (2, 4, 4), (2, 3, 5) и т. Д.

Идея состоит в том, чтобы рассматривать данную змею и лестничную площадку как ориентированный граф с числом вершин, равным количеству ячеек на доске. Проблема сводится к поиску кратчайшего пути в графе. Каждая вершина графа имеет ребро для следующих шести вершин, если в следующих 6 вершинах нет змеи или лестницы. Если у любой из следующих шести вершин есть змея или лестница, то ребро текущей вершины идет к вершине лестницы или хвоста змеи. Поскольку все ребра имеют одинаковый вес, мы можем эффективно найти кратчайший путь, используя поиск по ширине графа.

Ниже приводится реализация вышеуказанной идеи. Входные данные представлены двумя вещами, во-первых, это «N», которое является числом ячеек на данной доске, во-вторых, это массив «move [0… N-1]» размера N. Входное движение [i] равно -1 если нет змеи и лестницы от i, в противном случае move [i] содержит индекс ячейки назначения для змеи или лестницы в i.

C ++

// C ++ программа для поиска минимального количества бросков игральных костей, необходимых для
// достигаем последней клетки от первой клетки данной змеи и лестницы
// доска
#include<iostream>
#include <queue>

using namespace std;

  
// запись в очереди, используемая в BFS

struct queueEntry

{

    int v;     // номер вершины

    int dist;  // Расстояние этой вершины от источника

};

  
// Эта функция возвращает минимальное количество бросков кубиков, необходимое для
// Достичь последней ячейки от 0-й ячейки в игре со змеями и лестницами.
// move [] - массив размером N, где N - нет. ячеек на борту
// Если в ячейке i нет змеи или лестницы, то move [i] равно -1
// В противном случае move [i] содержит ячейку, в которой находится змея или лестница
// принимает.

int getMinDiceThrows(int move[], int N)

{

    // Граф имеет N вершин. Отметить все вершины как

    // не посещен

    bool *visited = new bool[N];

    for (int i = 0; i < N; i++)

        visited[i] = false;

  

    // Создать очередь для BFS

    queue<queueEntry> q;

  

    // Помечаем узел 0 как посещенный и ставим его в очередь.

    visited[0] = true;

    queueEntry s = {0, 0};  // расстояние 0 вершины также 0

    q.push(s);  // ставим в очередь 0-ю вершину

  

    // Делаем BFS, начиная с вершины с индексом 0

    queueEntry qe;  // Запись в очереди (qe)

    while (!q.empty())

    {

        qe = q.front();

        int v = qe.v; // вершина № записи в очередь

  

        // Если передняя вершина - вершина назначения,

        // мы сделали

        if (v == N-1)

            break;

  

        // Иначе удаляем переднюю вершину и ставим в очередь

        // его смежные вершины (или достижимые номера ячеек

        // через бросок костей)

        q.pop();

        for (int j=v+1; j<=(v+6) && j<N; ++j)

        {

            // Если эта ячейка уже посещена, тогда игнорируем

            if (!visited[j])

            {

                // В противном случае рассчитаем расстояние и отметим его

                // как посетил

                queueEntry a;

                a.dist = (qe.dist + 1);

                visited[j] = true;

  

                // Проверяем, есть ли змея или лестница в 'j'

                // затем хвост змеи или вершина лестницы

                // стать смежным с 'i'

                if (move[j] != -1)

                    a.v = move[j];

                else

                    a.v = j;

                q.push(a);

            }

        }

    }

  

    // Мы достигаем здесь, когда 'qe' имеет последнюю вершину

    // вернуть расстояние вершины в 'qe'

    return qe.dist;

}

  
// Программа драйвера для тестирования методов класса графа

int main()

{

    // Построим доску, приведенную на диаграмме выше

    int N = 30;

    int moves[N];

    for (int i = 0; i<N; i++)

        moves[i] = -1;

  

    // Лестницы

    moves[2] = 21;

    moves[4] = 7;

    moves[10] = 25;

    moves[19] = 28;

  

    // Змеи

    moves[26] = 0;

    moves[20] = 8;

    moves[16] = 3;

    moves[18] = 6;

  

    cout << "Min Dice throws required is " << getMinDiceThrows(moves, N);

    return 0;

}

Джава

// Java программа для поиска минимального количества игральных костей
// броски, необходимые для достижения последней ячейки с первого
// клетка данной змеи и лестничная доска

  

import java.util.LinkedList;

import java.util.Queue;

  

public class SnakesLadder 

{

    // запись в очереди, используемая в BFS

    static class qentry 

    {

        int v;// номер вершины

        int dist;// Расстояние этой вершины от источника

    }

  

    // Эта функция возвращает минимальное количество кубиков

    // броски, необходимые для достижения последней ячейки из 0-й ячейки

    // в игре змея и лестница. Move [] является массивом

    // размер N, где N нет. ячеек на борту Если есть

    // не змея или лестница из ячейки i, затем перемещаем [i]

    // is -1 В противном случае move [i] содержит ячейку, в которую

    // змея или лестница, в которую я иду.

    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;

  

        // Помечаем узел 0 как посещенный и ставим его в очередь.

        visited[0] = 1;

        q.add(qe);

  

        // Делаем BFS, начиная с вершины с индексом 0

        while (!q.isEmpty()) 

        {

            qe = q.remove();

            int v = qe.v;

  

            // Если передняя вершина является пунктом назначения

            // вершина, мы закончили

            if (v == n - 1)

                break;

  

            // В противном случае снимаем с фронта переднюю вершину и

            // ставим в очередь соседние вершины (или ячейку

            // числа достижимые через бросок костей)

            for (int j = v + 1; j <= (v + 6) && j < n; ++j) 

            {

                // Если эта ячейка уже посещена, тогда игнорируем

                if (visited[j] == 0)

                {

                    // Иначе вычисляем его расстояние и

                    // отметить его как посещенный

                    qentry a = new qentry();

                    a.dist = (qe.dist + 1);

                    visited[j] = 1;

  

                    // Проверяем, есть ли змея или лестница в 'j'

                    // затем хвост змеи или вершина лестницы

                    // стать смежным с 'i'

                    if (move[j] != -1)

                        a.v = move[j];

                    else

                        a.v = j;

                    q.add(a);

                }

            }

        }

  

        // Мы достигаем здесь, когда 'qe' имеет последнюю вершину

        // вернуть расстояние вершины в 'qe'

        return qe.dist;

    }

  

    public static void main(String[] args) 

    {

        // Построим доску, приведенную на диаграмме выше

        int N = 30;

        int moves[] = new int[N];

        for (int i = 0; i < N; i++)

            moves[i] = -1;

  

        // Лестницы

        moves[2] = 21;

        moves[4] = 7;

        moves[10] = 25;

        moves[19] = 28;

  

        // Змеи

        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 программа для поиска минимального числа
Количество бросков кубиков, необходимое для достижения последнего
# ячейка из первой ячейки данного
# змеиная и лестничная доска

  
# Запись в очереди, используемая в BFS

class QueueEntry(object):

    def __init__(self, v = 0, dist = 0):

        self.v = v

        self.dist = dist

  
'' 'Эта функция возвращает минимальное количество
броски костей, необходимые для. Дойти до последней клетки
из 0-й ячейки в игре змея и лестница.
move [] - массив размера N, где N
нет. ячеек на борту. Если нет
змея или лестница из клетки я, затем двигаться [я]
это -1. В противном случае перемещение [i] содержит ячейку в
к какой змее или лестнице я подхожу. '' '

def getMinDiceThrows(move, N):

      

    # Граф имеет N вершин. пометить все

    # вершины как не посещенные

    visited = [False] * N

  

    # Создать очередь для BFS

    queue = []

  

    # Отметить узел 0 как посещенный и поставить его в очередь

    visited[0] = True

  

    # Расстояние 0 вершины также 0

    # Поставить в очередь 0-ю вершину

    queue.append(QueueEntry(0, 0))

  

    # Сделать BFS, начиная с вершины с индексом 0

    qe = QueueEntry() # Запись в очереди (qe)

    while queue:

        qe = queue.pop(0)

        v = qe.v № вершины записи в очередь

  

        # Если передняя вершина является пунктом назначения

        # вершина, мы закончили

        if v == N - 1:

            break

  

        # В противном случае выровнять переднюю вершину

        # и поставить в очередь смежные вершины

        # (или номера ячеек, доступные через

        # бросок кубика)

        j = v + 1

        while j <= v + 6 and j < N:

          

            # Если эта ячейка уже посещена,

            # тогда игнорируй

            if visited[j] is False:

                  

                # В противном случае рассчитать его

                # расстояние и отметьте его

                # как посетил

                a = QueueEntry()

                a.dist = qe.dist + 1

                visited[j] = True

  

                # Проверьте, есть ли змея или лестница

                # на 'j', затем хвост змеи или верх

                № лестницы становится смежным с «я»

                a.v = move[j] if move[j] != -1 else j

  

                queue.append(a)

  

            j += 1

  

    # Мы достигаем здесь, когда у 'qe' есть последняя вершина

    # вернуть расстояние вершины в 'qe

    return qe.dist

  
# код водителя

N = 30

moves = [-1] * N

  
# Лестницы

moves[2] = 21

moves[4] = 7

moves[10] = 25

moves[19] = 28

  
# Змеи

moves[26] = 0

moves[20] = 8

moves[16] = 3

moves[18] = 6

  

print("Min Dice throws required is {0}".

       format(getMinDiceThrows(moves, N)))

  
# Этот код предоставлен Ajitesh Pathak

C #

// C # программа для поиска минимума
// необходимое количество бросков кубиков
// чтобы добраться до последней ячейки первой
// клетка данной змеи и лестничная доска

using System;

using System.Collections.Generic;

  

public class SnakesLadder 

{ 

    // запись в очереди, используемая в BFS

    public class qentry 

    { 

        public int v;// номер вершины

        public int dist;// Расстояние этой вершины от источника

    } 

  

    // Эта функция возвращает минимальное количество кубиков

    // броски, необходимые для достижения последней ячейки из 0-й ячейки

    // в игре змея и лестница. Move [] является массивом

    // размер N, где N нет. ячеек на борту Если есть

    // не змея или лестница из ячейки i, затем перемещаем [i]

    // is -1 В противном случае move [i] содержит ячейку, в которую

    // змея или лестница, в которую я иду.

    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; 

  

        // Помечаем узел 0 как посещенный и ставим его в очередь.

        visited[0] = 1; 

        q.Enqueue(qe); 

  

        // Делаем BFS, начиная с вершины с индексом 0

        while (q.Count != 0) 

        { 

            qe = q.Dequeue(); 

            int v = qe.v; 

  

            // Если передняя вершина является пунктом назначения

            // вершина, мы закончили

            if (v == n - 1) 

                break; 

  

            // В противном случае снимаем с фронта переднюю вершину и

            // ставим в очередь соседние вершины (или ячейку

            // числа достижимые через бросок костей)

            for (int j = v + 1; j <= (v + 6) && j < n; ++j) 

            { 

                // Если эта ячейка уже посещена, тогда игнорируем

                if (visited[j] == 0) 

                { 

                    // Иначе вычисляем его расстояние и

                    // отметить его как посещенный

                    qentry a = new qentry(); 

                    a.dist = (qe.dist + 1); 

                    visited[j] = 1; 

  

                    // Проверяем, есть ли змея или лестница в 'j'

                    // затем хвост змеи или вершина лестницы

                    // стать смежным с 'i'

                    if (move[j] != -1) 

                        a.v = move[j]; 

                    else

                        a.v = j; 

                    q.Enqueue(a); 

                } 

            } 

        } 

  

        // Мы достигаем здесь, когда 'qe' имеет последнюю вершину

        // вернуть расстояние вершины в 'qe'

        return qe.dist; 

    } 

  

    // Код драйвера

    public static void Main(String[] args) 

    { 

        // Давайте построим доску

        // дано на диаграмме выше

        int N = 30; 

        int []moves = new int[N]; 

        for (int i = 0; i < N; i++) 

            moves[i] = -1; 

  

        // Лестницы

        moves[2] = 21; 

        moves[4] = 7; 

        moves[10] = 25; 

        moves[19] = 28; 

  

        // Змеи

        moves[26] = 0; 

        moves[20] = 8; 

        moves[16] = 3; 

        moves[18] = 6; 

  

        Console.WriteLine("Min Dice throws required is " + 

                        getMinDiceThrows(moves, N)); 

    } 

} 

  
// Этот код предоставлен 29AjayKumar


Выход:

Min Dice throws required is 3

Временная сложность вышеупомянутого решения составляет O (N), поскольку каждая ячейка добавляется и удаляется только один раз из очереди. И типичная операция постановки в очередь или удаления занимает O (1) времени.

Эта статья предоставлена Сиддхартом . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проблема змеи и лестницы

0.00 (0%) 0 votes