Resolva o Quebra-Cabeças
Dado um tabuleiro que contém os números 1, 2, 3, …, 9, pede-se que executes uma sequência de trocas para chegar ao seguinte arranjo:
Em cada movimento, podes trocar dois vizinhos (vizinhos em sentido horizontal ou vertical). Qual será o número mínimo de movimentos necessários para obter o arranjo desejado?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Entrada
A entrada contém 3 linhas, cada uma com 3 números, que representam o tabuleiro inicial.
Saída
O programa deve imprimir o número mínimo de movimentos necessários para obter o tabuleiro 1, 2, 3, …, 9.
Exemplos
Entrada | Saída |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB