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 є пробіл.