Hop - Не Иди
KERMIT THE FROG — это классическая видеоигра с простым управлением и целью, но требующая значительного уровня мышления.
Вы управляете анимированной лягушкой, которая может ходить и прыгать, как вперед, так и назад. Лягушка находится в пространстве между непрерывной линией плиток. Каждая плитка окрашена в черный с одной стороны и в белый с другой. Лягушка может перемещаться (вперед или назад) на соседнюю плитку (перед ней или за ней).
Когда лягушка проходит по плитке, плитка перемещается на место, где стояла лягушка. Например, на соседней фигуре у лягушки две плитки позади и три впереди. Мы будем использовать обозначение BWFBBW для описания этой ситуации, где F обозначает пространство (где стоит лягушка), B — это плитка с черной стороной наверху, а W — плитка с белой стороной наверху. Направление вперед — слева направо. Если лягушка пойдет вперед, получится ситуация BWBFBW. Аналогичное поведение происходит, когда лягушка идет назад, плитка позади лягушки перемещается на место, где стояла лягушка. Лягушка также может прыгать через плитки. Лягушка может прыгнуть через соседнюю плитку, приземляясь на плитку рядом с ней. Например, если лягушка прыгнет назад, она приземлится на первую (самую левую) плитку, и плитка переместится на место, где стояла лягушка. Кроме того, плитка перевернется. Например, прыжок назад на фигуре приведет к ситуации: FWWBBW. Вам предлагается написать программу, чтобы определить минимальное количество ходов (шагов или прыжков), необходимых для преобразования одной конфигурации плиток в другую.
Входные данные
Ваша программа будет протестирована на одном или нескольких тестах. Каждый тест задается одной строкой, которая указывает строку S, представляющую начальное расположение плиток. S — это непустая строка длиной не более 100 символов и состоит из букв "B", "W" и ровно одной "F". Последняя строка входного файла содержит один или несколько символов "-" (минус).
Выходные данные
Для каждого теста выведите следующую строку:
k. M
Где k — номер теста (начиная с единицы), а M — минимальное количество ходов, необходимых для преобразования данного расположения в такое, в котором нет белых плиток (s) между черными плитками. Лягушка может находиться где угодно. M равен -1, если задача не может быть решена менее чем за 10 ходов.
Примечание: Перед M стоит пробел.