Кубики#3359
У коробці 3 \times 3 \times 1 (ширина×довжина×висота), яку встановлено горизонтально на столі, в один шар лежать вісім кубиків 1 \times 1 \times 1 таким чином, що їх грані паралельні граням коробки. У кожного кубика з граней білі і одна - червона.
За один хід Вам дозволено перекотити довільний з кубиків (сусідніх з вільним місцем) на вільне місце через його ребро. Фінальне положення - вільне місце знаходиться у центрі коробки, а червоні грані усіх кубиків знаходяться у напрямку спостерігача (вважається, що Ви дивитесь на коробку згори). Ваша задача визначити мінімальну кількість ходів, необхідних для перетворення початкового положення у фінальне.
Вхідний файл містить рядки по символи у кожному. Кожен символ показує положення червоної грані відповідного кубика або вільне місце у початковому положенні:
. - вільне місце
+ - червона грань у напрямку спостерігача
* - червона грань у напрямку від спостерігача (до дна коробки)
U - червона грань зверху
D - червона грань знизу
L - червона грань ліворуч
R - червона грань праворуч
Вихідний файл повинен містити одне ціле число - відповідь до задачі. Якщо таке перетворення неможливе, то необхідно вивести .
Приклад 1
Задача ґрунтується на "Відкритому особистому чемпіонаті Європейського інституту енергетики, Центральне Місто, 20.05.2011."