Решение задачи #15. Python Яндекс CodeRun, Путь спелеолога

Вариант решения задачи на языке программирования Python с Яндекс CodeRun.
Категория: Алгоритмы.
Название задачи: Путь спелеолога.
Статус решения: "Решено".

Условие задачи:
Алгоритм. Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N3N3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

Решение:

Python

import sys

def main():
    """Функция main решает задачу поиска минимального пути спелеолога к поверхности."""

    # Считываем входные данные
    input_lines = sys.stdin.read().splitlines()  # Читаем все строки из входных данных
    N = int(input_lines[0])  # Первое число - размерность пещеры (N)
    
    # Создаем трехмерный массив для представления пещеры
    cave = []
    current_block = []
    for line in input_lines[1:]:
        if line.strip() == "":  # Если встретилась пустая строка, это разделитель между блоками
            if current_block:  # Если блок не пустой, добавляем его в пещеру
                cave.append(current_block)
                current_block = []  # Очищаем текущий блок для следующего уровня
        else:
            current_block.append(list(line))  # Добавляем строку в текущий блок
    
    # После цикла добавляем последний блок, если он есть
    if current_block:
        cave.append(current_block)

    # Находим начальную позицию спелеолога (S)
    start_position = None
    for z in range(N):
        for y in range(N):
            for x in range(N):
                if cave[z][y][x] == 'S':  # Если нашли символ 'S'
                    start_position = (z, y, x)
                    break
            if start_position:
                break
        if start_position:
            break

    # Инициализируем очередь для BFS (поиск в ширину)
    from collections import deque
    queue = deque()
    queue.append((start_position, 0))  # Кортеж содержит позицию и количество шагов

    # Множество посещенных клеток
    visited = set()
    visited.add(start_position)

    # Направления движения (dx, dy, dz) - шесть возможных направлений
    directions = [
        (0, 0, 1), (0, 0, -1),  # Вверх и вниз по z
        (0, 1, 0), (0, -1, 0),  # Вправо и влево по y
        (1, 0, 0), (-1, 0, 0)   # Вперед и назад по x
    ]

    # Выполняем поиск в ширину (BFS)
    while queue:
        (current_z, current_y, current_x), steps = queue.popleft()

        # Если достигли верхнего уровня пещеры, то выходим
        if current_z == 0 and cave[current_z][current_y][current_x] == '.':
            print(steps)  # Выводим количество шагов
            return

        # Проверяем все возможные направления движения
        for dz, dy, dx in directions:
            new_z, new_y, new_x = current_z + dz, current_y + dy, current_x + dx

            # Проверяем, что новые координаты находятся внутри пещеры
            if 0 <= new_z < N and 0 <= new_y < N and 0 <= new_x < N:
                # Проверяем, что новая клетка свободна и еще не посещена
                if cave[new_z][new_y][new_x] != '#' and (new_z, new_y, new_x) not in visited:
                    visited.add((new_z, new_y, new_x))  # Отмечаем как посещенную
                    queue.append(((new_z, new_y, new_x), steps + 1))  # Добавляем в очередь с увеличенным количеством шагов

# Запускаем функцию main
if __name__ == "__main__":
    main()

Объяснение кода

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

Поиск начальной позиции:
Мы проходим по всем клеткам пещеры, чтобы найти позицию спелеолога (S). Как только она найдена, процесс останавливается.

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

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

Условие завершения:
Как только мы достигаем верхнего уровня (z == 0) и попадаем в свободную клетку (.), мы выводим количество шагов и завершаем работу программы.

Этот подход гарантирует, что мы найдем минимальное количество шагов для выхода на поверхность, так как BFS всегда находит кратчайший путь в графе.

Источник решения: hdhai.com