Кубики
У коробці 3×3×1 (ширина×довжина×высота), яку встановлено горизонтально на столі в один шар лежать вісім кубиків 1×1×1 таким чином, що їх грані паралельні граням коробки. У кожного кубика 5-ть з 6-ти граней білі і одна - червона.
За один хід Вам дозволено перекотити довільний з кубиків (сусідніх з вільним місцем) на вільне місце через його ребро. Фінальне положення - вільне місце знаходиться у центрі коробки, а червоні грані усіх кубиков знаходяться у напрямку спостерігача (вважається, що Ви дивитесь на коробку згори). Ваша задача визначити мінімальну кількість ходів, необхідних для перетворення початкового положення у фінальне.
Вхідні дані
Вхідний файл містить 3 рядки по 3 символи у кожному. Кожен символ показує положення червоної грані відповідного кубика або вільне місце у початковому положенні:
. - вільне місце
+ - червона грань у напрямку спостергіача
* - червона грань у напрямку від спостергігача (до дна коробки)
U - червона грань зверху
D - червона грань знизу
L - червона грань ліворуч
R - червона грань праворуч
Вихідні дані
Вихідний файл повинен містити одне ціле число - відповідь до задачі. Якщо таке перетворення неможливе, то необхіно вивести -1.