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

Не решаласьЛёгкая

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

Формат ввода

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

Формат вывода

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

Примечание

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

Ограничения

Ограничение времени

1 с

Ограничение памяти

64 МБ

Пример 1

Ввод
3

###
###
.##

.#.
.#S
.#.

###
...
###
Вывод
6

Теги

Нужно войти, чтобы отправить решение.Войти
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
/*
Для чтения входных данных необходимо получить их
из стандартного потока ввода (stdin).
Данные во входном потоке соответствуют описанному
в условии формату. Обычно входные данные состоят
из нескольких строк.

Можно использовать несколько функций для чтения из stdin:
* scanf() -- читает данные из потока;
* fgets() -- читает строку из потока;
* gets() -- читает строку из потока до символа '\n'.

Чтобы прочитать из строки стандартного потока:
* число -- int var; scanf("%d", &var);
* строку -- char svar[100]; scanf("%s", svar);
* массив чисел известной длины --
int len; scanf("%d", &len);
int* arr = (int*) malloc(len * sizeof(int));
for (int i = 0; i < len; ++i)
scanf("%d", &arr[i]);
* последовательность слов до конца файла --
char word[100];
while (scanf("%s", word) == 1) {
// do something with word
}

Чтобы вывести результат в стандартный поток вывода (stdout),
можно использовать функцию printf().

Возможное решение задачи "Вычислите сумму A+B":


int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", a + b);
*/

return 0;
}