Resuelve el Rompecabezas
Dado un tablero de que contiene los números 1, 2, 3, …, 9, se te pide realizar una secuencia de intercambios para obtener el siguiente tablero:
En cada movimiento, puedes intercambiar dos vecinos (vecinos en sentido horizontal o vertical). ¿Cuál sería el número mínimo de movimientos necesarios para lograr el tablero deseado?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Entrada
La entrada contiene 3 líneas, cada una con 3 números que representan el tablero inicial.
Salida
El programa debe imprimir el número mínimo de movimientos requerido para obtener el tablero con los números 1, 2, 3, …, 9.
Ejemplos
Entrada | Salida |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB