Задача №113819. Портал

Главный герой этого задания, Челл, должна решить новую головоломку ГЛаДОС. Челл находится в комнате, представленной в виде поля N × M ( N строк и M столбцов). Каждая клетка может являться одним из следующего:

  1. Стена (помечена символом «#»)
  2. Клетка, где находится Челл на старте (помечена символом « C »)
  3. Выход, куда Челл нужно попасть для решения головоломки (помечена символом « F »)
  4. Пустая клетка (помечена символом « . »)

Челл носит с собой так называемую «портальную пушку», которая может создавать порталы на стенах. Герой может делать следующее:

  1. Передвинуться вверх, вниз, влево или вправо на одну клетку (не может пройти, если в этой клетке стена), это действие занимает одну единицу времени.
  2. Выстрелить «портальной пушкой» вверх, вниз, влево или вправо. Портал создастся на ближайшей по направлению выстрела стене. Он будет находится на краю стены в месте попадания. В каждый момент на поле может быть активными не более двух порталов . Если создаётся третий портал, то самый ранний из открытых перестаёт быть активным. Нельзя создать портал там, где он уже есть. Это действие происходит мгновенно и занимает ноль единиц времени.
  3. Пройти в портал, расположенный на стене, если существует второй портал. Она выйдет в клетке перед вторым порталом. Это действие занимает одну единицу времени.

Челл хочет знать минимальное время в единицах, за которое она может попасть к выходу, то есть достигнуть клетки с названием « F »

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

В первой строке заданы два натуральных числа N и M ( 4 ≤ N , M ≤ 500 ) В каждой из следующих N строк заданы M символов — игровое поле. Комната всегда ограждена стенами по сторонам, символы « C » и « F » встречаются по одному разу.

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

Выведите минимальное время в единицах, за которое можно решить головоломку, или выведите «nemoguce» («Невозможно» по-хорватски), если решить головоломку нельзя.

Система оценки

Программы, верно работающее на тестах, где 4 ≤ N , M ≤ 15 оцениваются в 50 баллов

Примечание

Пояснения ко второму примеру:

Примеры
Входные данные
4 4
####
#.F#
#C.#
####
Выходные данные
2
Входные данные
6 8
########
#.##..F#
#C.##..#
#..#...#
#.....##
########
Выходные данные
4
Входные данные
4 5
#####
#C#.#
###F#
#####
Выходные данные
nemoguce
Сдать: для сдачи задач необходимо войти в систему