Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Только направо

(Время: 1 сек. Память: 16 Мб Сложность: 60%)

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

Входные данные

В первой строке входного файла INPUT.TXT через пробел записаны числа N и M (4 ≤ N, M ≤ 20) – количество строк и столбцов в карте лабиринта. В каждой из следующих N строк записано по M символов, задающих эту карту. Символ «S» обозначает положение Змея Горыныча, символ «F» – точку выхода из лабиринта, символ «X» – стенку. Пробелами обозначены пустые клетки. Гарантируется, что лабиринт окружен стенами, и Змей Горыныч всегда сможет выйти из лабиринта. Перед началом движения Змей Горыныч может сориентироваться по любому из 4 направлений (вверх, вниз, влево или направо).

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число – расстояние, которое придется пройти Змею Горынычу.

Пример

INPUT.TXTOUTPUT.TXT
110 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

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Путь
 B. Один конь
 C. Табличка
 D. Грядки
 E. Звезда
 F. Морской бой - 3
 G. Два коня
 H. Лабиринт с тигром
 I. Алхимия
 J. Игра - 4
 K. Игра Jammed
 L. Числа
 M. Кладоискатель
 N. Водолей
 O. Lines - 2
 P. Ладья в лабиринте
 Q. Игрушечный лабиринт
 R. Лабиринт
 S. Мосты
 T. Цивилизация
 U. Только направо
 V. Герои
 W. Лабиринт минотавра
 X. Наименьшее кратное
 Y. Космические исследования
 Z. Кубик Рубика

Красноярский краевой Дворец пионеров, (c)2006 - 2022, ICQ: 151483, E-mail: admin@acmp.ru



как пилить цсп плиту лобзиком