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