Risolvi il rompicapo
Data una griglia che contiene i numeri 1, 2, 3, …, 9, ti viene chiesto di effettuare una serie di operazioni di scambio per ottenere la seguente griglia:
A ogni mossa, puoi scambiare due celle adiacenti (adiacenti in orizzontale o in verticale). Qual è il numero minimo di mosse necessarie per raggiungere la configurazione desiderata?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Input
L’input contiene 3 righe, ognuna con 3 numeri che rappresentano la griglia iniziale.
Output
Il programma deve stampare il numero minimo di mosse necessario per ottenere la griglia 1, 2, 3, …, 9.
Esempi
Input | Output |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB