Розмальований Куб
Як тільки кільце влади опинилося у Фродо, Гендальф негайно вирушив до Сарумана, голови свого ордену, щоб порадитися. Саруман не погодився з Гендальфом, що кільце слід знищити. Він вирішив не відпускати Гендальфа, щоб той не допоміг Фродо, і замкнув його в найвищій кімнаті своєї темної вежі в Ізенгарді. Щоб зайняти Гендальфа, Саруман поставив у кімнаті єдині двері, які можна було відкрити, лише розгадавши загадку.
Після недовгих пошуків виходу з кімнати, Гендальф помітив дуже дивний замок на дверях, які, здавалося, вели на дах вежі. Замок був стандартним шестигранним кубом без позначок на жодній з його граней. Він був розміщений на вершині сітки розміром m×n. Сітка мала рівно шість квадратів з фарбою. Гендальф помітив, що коли він котив порожню грань куба на квадрат з позначками, позначки переносилися з сітки на грань куба. Коли куб котився на квадрат без позначок, а контактна грань куба мала позначку, позначка переносилася з куба на сітку. Якщо куб котився через квадрат на сітці з позначкою, і контактна грань куба також мала позначку, нічого не відбувалося.
Гендальф дійшов висновку, що двері на дах можна відкрити, якщо куб буде прокочений послідовністю ходів до цільового квадрата так, щоб усі позначки з сітки були перенесені на куб. Більше того, щоб уникнути пастки Сарумана, він (правильно) здогадався, що йому потрібно виконати це за мінімальну кількість ходів.
З огляду на початкову конфігурацію фарби на квадратах, початкове розташування куба та бажане цільове розташування, яка мінімальна кількість ходів, яку Гендальф повинен виконати, щоб привести куб до цільового стану з фарбою на всіх його сторонах?
Для першого прикладу (див. нижче) зразкове рішення буде: вниз, вправо, вправо, вгору, вправо, вправо, вниз, вліво, вправо, вліво.
Вхідні дані
Вхідний файл міститиме кілька тестових випадків. Кожен тестовий випадок складатиметься з m×n сітки символів, де m і n знаходяться в межах від 2 до 20. У кожному тестовому випадку порожні місця будуть позначені '.', пофарбовані квадрати 'P', незаконні квадрати '#', початкова позиція куба 'C', а цільовий квадрат 'G'. Завжди буде рівно 6 'P', рівно один 'C', рівно один 'G', і не більше 12 '.'. Вхідні тестові випадки будуть розділені одним порожнім рядком. Вхід завершується кінцем файлу.
Вихідні дані
Для кожного вхідного тестового випадку надрукуйте мінімальну кількість ходів, необхідних для досягнення цільового стану. Якщо досягти цього стану неможливо, надрукуйте -1.