03/12/2024 22:33:52

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

12. Путь спелеолога

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Ввод

В первой строке содержится число `N\ (1\ ≤\ N\ ≤\ 30)`. Далее следует `N` блоков. Блок состоит из пустой строки и `N` строк по `N` символов: # — обозначает клетку, заполненную камнями, точка — свободную клетку. Начальное положение спелеолога обозначено заглавной буквой S. Первый блок представляет верхний уровень пещеры, достижение любой свободной его клетки означает выход на поверхность. Выход на поверхность всегда возможен.

Вывод

Вывести одно число – длину пути до поверхности.

Пример ввода

3

###
###
.##

.#.
.#S
.#.

###
...
###

Пример вывода

Пояснение: Нужно спуститься на уровень вниз, сделать два движения на запад, подняться на уровень вверх, сделать движение на юг, подняться на уровень вверх.

Источник: Всероссийская студенческая олимпиада, Воронеж, 2003, Меньшиков

03/07/2006	Лето 2006 дорешивание ( 7E)
17/07/2006	Лето 2006 - 7 (E)
14/11/2007	Занятие 10 (D)
13/03/2010	Занятие 10 (C)
09/12/2010	Сборы: Общий итог (4F)
30/12/2010	Сборы 4: Домашнее задание (B)
17/11/2012	Занятие 10 (A)
07/07/2021	Лето 2021-5 (C)
04/07/2022	Лето 2022-4 (C)
14/09/2022	Пути в графах (повторение) (проводит BOGAT) (G)
04/12/2024	ЦОП1: Графы 2 (проводит BOGAT) (D)