Résoudre le Casse-tête
Étant donné une grille contenant les nombres 1, 2, 3, …, 9, vous devez effectuer une série d’opérations d’échange afin d’obtenir la grille suivante :
À chaque coup, vous pouvez échanger deux cases voisines (adjacentes soit horizontalement, soit verticalement). Quel est le nombre minimal de mouvements requis pour atteindre la grille demandée ?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Input
L’entrée contient 3 lignes, chacune comprenant 3 nombres représentant la grille initiale.
Output
Le programme doit afficher le nombre minimal de mouvements requis pour obtenir la grille 1, 2, 3, …, 9.
Examples
Entrée | Sortie |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB