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