Продолжаю решать задачи на веб-сервисе «CodeRun» от «Яндекса». В этот раз опишу, как решил задачу из группы «легких», которая называется «Путь спелеолога». Задача интересна своей трехмерностью, я создал изображения с трехмерной моделью пещеры.

Предыдущие три поста из четырех в этой серии:

  1. C++: ход конем,
  2. C++: длина кратчайшего пути,
  3. C++: задача с блохами.

Формулировка задачи

Есть пещера в виде куба. Этот куб состоит из кубических клеток и имеет размеры N × N × N клеток. Каждая кубическая клетка может быть пустой или полностью заполненной камнем. В одной из пустых кубических клеток находится спелеолог. Требуется найти минимальное количество перемещений по кубическим клеткам, нужное спелеологу, чтобы выйти на поверхность (достичь любой пустой кубической клетки верхнего слоя пещеры). Переход из одной кубической клетки в другую возможен, если обе эти клетки пустые и имеют общую грань для перехода.

При получении данных в первой строке ввода содержится число N. Далее разделенные пустыми строками следуют N слоев куба, каждый размерами N × N, от верхнего к нижнему. Пустые кубические клетки обозначают символом . (точка). Заполненные камнем кубические клетки обозначают символом #. Кубическую клетку со спелеологом обозначают символом S. Выход на поверхность всегда возможен.

Пример ввода данных и вывода результата:

3

###
###
.##

.#.
.#S
.#.

###
...
###
6

В этом примере задана пещера размерами 3 × 3 × 3 кубических клеток. В последней строке примера программа вывела число 6 — минимальное число перемещений для достижения спелеологом выхода для заданной пещеры и заданных координат спелеолога.

Я воспользовался известным веб-сервисом «Tinkercad» (я о нем писал ряд постов, например) и сделал визуализацию заданной в этом примере пещеры. Вот разложение по слоям (спелеолога обозначил красным шариком):

Вот пещера в «собранном» виде:

Пустая кубическая клетка в верхнем слое пещеры только одна, то есть существует единственный выход из пещеры. Чтобы добраться до этого выхода, спелеологу нужно сделать следующие перемещения: на одну клетку вниз, на две клетки влево, на одну клетку вверх, на одну клетку ближе к наблюдателю и на одну клетку вверх (всего нужно пройти 6 кубических клеток).

Алгоритм решения задачи

Эта задача мне сразу напомнила о популярнейшей игре Minecraft.

Мои родители учились на геологов и на летних каникулах занимались в качестве любителей спелеологией (наука о пещерах и их исследовании) в Уральских горах. Моё детство было заполнено просмотром фотографий и диапозитивов, на которых были запечатлены лабиринты пещер, горы и люди в касках с рюкзаками и палатками.

В этот раз решение задачи не составило особых трудностей. Я просто взял идеи и инструменты, обкатанные при решении двух предыдущих задач, и подстроил их под условия данной задачи.

В данном случае кубические клетки я считаю вершинами графа. Ребрами графа становятся возможные переходы между кубическими клетками. Возможных переходов у одной кубической клетки может быть до 6 штук (по числу граней кубической клетки). При поиске ребер проверяю, не ведут ли переходы за пределы куба пещеры и не ведут ли переходы в заполненные камнем кубические клетки.

Как и в предыдущих задачах, использую на графе алгоритм поиска в ширину. Начальная вершина — клетка со спелеологом, конечная вершина — любая пустая клетка верхнего слоя пещеры, до которой спелеологу будет добраться быстрее всего.

С точки зрения строения графа нет никакой разницы между двумерным полем с блохами из предыдущей задачи и трехмерным кубом пещеры из этой задачи. Алгоритм поиска в ширину работает так же. Единственное, что усложняется — это структура для хранения исходных данных. В предыдущей задаче я использовал вектор векторов (двумерная структура), в этой задаче — вектор векторов векторов (трехмерная структура).

Моя реализация решения на C++

При посимвольном получении данных из консоли через объект std::cout автоматически игнорируются пробельные символы (пробелы, символы новой строки, символы горизонтальной табуляции). Поэтому сложностей при получении данных о строении пещеры и координатах спелеолога в пещере в указанном в условиях задачи виде не возникает. (Поначалу я думал, что здесь придется что-то придумывать, но всё решилось очень просто.)

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

Во-первых, можно подсчитывать длину кратчайшего пути в цикле самого поиска, прибавляя единичку к длине при каждом расширении поиска. Во-вторых, можно подсчитать длину кратчайшего пути после окончания поиска, восстановив кратчайший путь, двигаясь от конечной вершины к начальной по записанным родителям вершин. Первый вариант более экономичный, но не позволяет получить кратчайший путь в пошаговом виде. Второй вариант кроме длины кратчайшего пути позволяет получить его в пошаговом виде. Я выбрал второй вариант, хотя в данном случае это было необязательно.

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

#include <iostream>
#include <vector>   // для std::vector
#include <queue>    // для std::queue

// координаты (отсчет с 0) кубической клетки пещеры
struct vertex_coords
{
    int z; // номер слоя куба (от верхнего к нижнему)
    int y; // номер ряда в слое куба (от верхнего к нижнему)
    int x; // номер столбца в слое куба (слева направо)
};

// описание вершины графа (кубическая клетка пещеры)
struct vertex
{
    bool inQueue; // находится в очереди или нет
    bool visited; // посещена или нет
    bool isAVoid; // пустая или заполненная камнем
    vertex_coords parent; // откуда в эту клетку пришел спелеолог
};

int main()
{
    // получить размер куба, представляющего пещеру
    int N{};
    std::cin >> N;

    // создать трехмерную таблицу вершин графа (кубических клеток)
    // с инициализацией вершин, изначально все вершины не в очереди (false),
    // не посещены (false) и заполнены камнем (false),
    // родитель пока не известен { -1, -1, -1 }
    std::vector<std::vector<std::vector<vertex>>> cave(
        N,
        std::vector<std::vector<vertex>>(
            N,
            std::vector<vertex>(N, { false, false, false, { -1, -1, -1 } })
        )
    );
    // координаты текущей кубической клетки при обходе клеток
    vertex_coords coords{ 0, 0, 0 };

    // получить информацию о строении пещеры и координатах спелеолога
    for (int z{}; z < N; z++)
    {
        for (int y{}; y < N; y++)
        {
            for (int x{}; x < N; x++)
            {
                char ch{};
                std::cin >> ch;
                switch (ch)
                {
                    //case '#': // уже сделано при инициализации пещеры
                    case '.':
                        cave[z][y][x].isAVoid = true;
                        break;
                    case 'S':
                        cave[z][y][x].isAVoid = true;
                        // координаты начала поиска (координаты спелеолога)
                        coords = { z, y, x };
                        break;
                }
            }
        }
    }

    // создать пустую очередь и поместить в нее координаты спелеолога
    std::queue<vertex_coords> qu;
    qu.push(coords);
    cave[coords.z][coords.y][coords.x].inQueue = true;

    // выполнить поиск в ширину, начиная от кубической клетки со спелеологом
    // до нахождения любой из пустых клеток верхнего слоя пещеры
    do
    {
        // извлечь из очереди клетку и пометить ее как посещенную
        coords = qu.front();
        qu.pop();
        cave[coords.z][coords.y][coords.x].inQueue = false;
        cave[coords.z][coords.y][coords.x].visited = true;

        // если извлеченная клетка является искомой (из верхнего слоя пещеры)
        if (coords.z == 0)
        {          // выход из бесконечного цикла
            break; // по условиям задачи он здесь будет обязательно
        }
        else // извлеченная клетка НЕ является искомой
        {
            // добавить в очередь всех потомков извлеченной клетки, которые
            // не посещены и не находятся в очереди
            // (у кубической клетки может быть до 6 потомков по числу граней,
            // но нужно проверить, что не происходит выхода за стены пещеры и
            // что клетка-потомок не заполнена камнем)
            const int num_faces{ 6 };
            int dz[num_faces]{ -1, 1,  0, 0,  0, 0 }; // сдвиг по z
            int dy[num_faces]{  0, 0, -1, 1,  0, 0 }; // сдвиг по y
            int dx[num_faces]{  0, 0,  0, 0, -1, 1 }; // сдвиг по x
            vertex_coords par_coords{ coords }; // запомнить клетку-родителя
            for (int face{}; face < num_faces; face++)
            {
                coords = { par_coords.z + dz[face], par_coords.y + dy[face],
                           par_coords.x + dx[face] };
                if (coords.z >= 0 && coords.z < N &&
                    coords.y >= 0 && coords.y < N &&
                    coords.x >= 0 && coords.x < N &&
                    cave[coords.z][coords.y][coords.x].isAVoid &&
                    !cave[coords.z][coords.y][coords.x].visited &&
                    !cave[coords.z][coords.y][coords.x].inQueue)
                {
                    qu.push(coords);
                    cave[coords.z][coords.y][coords.x].inQueue = true;
                    cave[coords.z][coords.y][coords.x].parent = par_coords;
                }
            }
        }
    } while (true); // бесконечный цикл

    // восстановить путь, подсчитывая его длину, и вывести результат
    int path_len{};
    for (vertex_coords v{ coords }; cave[v.z][v.y][v.x].parent.z != -1;
         v = cave[v.z][v.y][v.x].parent)
    {
        path_len++;
    }
    std::cout << path_len << '\n';

    return 0;
}

Эта реализация успешно прошла автоматическую проверку на веб-сервисе «CodeRun» от «Яндекса».