Обход лабиринта Змеем Горынычем только направо

@Alex_frai · Регистрация: 28.10.2015

Author24 — интернет-сервис помощи студентам

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

Входные данные
В первой строке через пробел записаны числа r и c (4 ≤ r, c ≤ 20) - количество строк и столбцов в карте лабиринта. В каждой из следующих r строк записано по c символов, задающих эту карту. Символ S обозначает положение Змея Горыныча, символ F - точку выхода из лабиринта, символ X - стенку. Пробелами обозначены проходимые клетки. Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).

Выходные данные
Выведите единственное число - расстояние, которое придется пройти Змею Горынычу. Гарантируется, что он всегда сможет выйти из лабиринта.

входные данные
10 14

Код

XXXXXXXXXXXXXX
X                  XXX
X  XFXXXXX       X
XXX     XX    XX  X
X  S                  X
XX    XXXXXX  X  X
X               X  X  X
X  X           X  X  X
XXX  XX             X
XXXXXXXXXXXXXX

выходные данные
29

@Alex_frai 0 / 0 / 0 Регистрация: 28.10.2015 Сообщений: 3
		1
	Обход лабиринта Змеем Горынычем только направо 22.12.2015, 23:57. Показов 1762. Ответов 0 Метки нет (Все метки) Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира, левая голова Змея соображает плохо. Поэтому Змей Горыныч может поворачивать направо и идти прямо, но не может поворачивать налево и разворачиваться на месте. Помогите Змею Горынычу определить длину кратчайшего пути до выхода из лабиринта. Входные данные В первой строке через пробел записаны числа r и c (4 ≤ r, c ≤ 20) - количество строк и столбцов в карте лабиринта. В каждой из следующих r строк записано по c символов, задающих эту карту. Символ S обозначает положение Змея Горыныча, символ F - точку выхода из лабиринта, символ X - стенку. Пробелами обозначены проходимые клетки. Гарантируется, что лабиринт окружен стенами. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо). Выходные данные Выведите единственное число - расстояние, которое придется пройти Змею Горынычу. Гарантируется, что он всегда сможет выйти из лабиринта. входные данные 10 14 Код XXXXXXXXXXXXXX X XXX X XFXXXXX X XXX XX XX X X S X XX XXXXXX X X X X X X X X X X X XXX XX X XXXXXXXXXXXXXX выходные данные 29 0

	22.12.2015, 23:57