\documentclass{maratona}

\begin{document}
\begin{ProblemaAutor}{}{6 Puzzle}{1}{256}{Leetcode 773}

Imagine um pequeno tabuleiro de tamanho \(2 \times 3\), contendo cinco peças numeradas de \(1\) a \(5\) e uma casa vazia representada por \(0\). O jogador pode mover a casa vazia trocando-a com uma peça adjacente, seja nas direções horizontal ou vertical. Assim, cada jogada corresponde a uma troca entre o \(0\) e um número vizinho.

O objetivo é organizar o tabuleiro de modo que as peças fiquem na seguinte disposição:
\[
\begin{bmatrix}
1 & 2 & 3\\[4pt]
4 & 5 & 0
\end{bmatrix}.
\]

Dado um estado inicial do tabuleiro, determine o número mínimo de jogadas necessárias para alcançar o estado resolvido. Caso não exista sequência possível de movimentos que leve ao arranjo final, imprima \(-1\).

\Entrada

A entrada consiste em duas linhas, cada uma contendo exatamente três dígitos distintos de 0 a 5, onde
a primeira linha descreve a linha superior do tabuleiro, e a segunda linha descreve a linha inferior.

\Saida

Imprima um único inteiro representando o número mínimo de movimentos necessários para transformar o estado inicial no estado resolvido.
Se o estado não puder ser resolvido, imprima \(-1\).

\ExemploEntrada
\begin{Exemplo}
\texttt{412} & \texttt{5}\\
\texttt{503} & \\
\rowcolor{gray!20}\texttt{123} & \texttt{-1}\\
\rowcolor{gray!20}\texttt{540} & \\
\texttt{123} & \texttt{1}\\
\texttt{405} & \\
\end{Exemplo}



\Notas

Explicação primeiro caso de teste:
\newline
A menor sequência de movimentos tem comprimento \(5\). Uma possível sequência de estados é mostrada abaixo:
\newline
\[
\begin{aligned}
&\begin{bmatrix}4&1&2\\5&0&3\end{bmatrix}\to
\begin{bmatrix}4&1&2\\0&5&3\end{bmatrix}\to
\begin{bmatrix}0&1&2\\4&5&3\end{bmatrix}\to\\
&\begin{bmatrix}1&0&2\\4&5&3\end{bmatrix}\to
\begin{bmatrix}1&2&0\\4&5&3\end{bmatrix}\to
\begin{bmatrix}1&2&3\\4&5&0\end{bmatrix}.
\end{aligned}
\]
\newline
Explicação segundo caso de teste:
\newline
É possível provar que nenhuma sequência de estados irá atingir a configuração desejada. Resultado: \(-1\).\end{ProblemaAutor}
\end{document}