Löse das Rätsel
Gegeben ist ein Gitter mit den Zahlen 1, 2, 3, …, 9. Sie sollen eine Abfolge von Tauschoperationen durchführen, um das folgende Gitter zu erhalten:
Bei jedem Zug können Sie zwei benachbarte Felder (benachbart in horizontaler oder vertikaler Richtung) miteinander vertauschen. Wie viele Züge sind mindestens notwendig, um das gewünschte Gitter zu erreichen?
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
Eingabe
Die Eingabe besteht aus 3 Zeilen, von denen jede 3 Zahlen enthält, die das anfängliche Gitter darstellen.
Ausgabe
Das Programm soll die minimale Anzahl an Zügen ausgeben, die benötigt wird, um das Gitter 1, 2, 3, …, 9 herzustellen.
Beispiele
Eingabe | Ausgabe |
2 1 3
7 5 9
8 4 6 | 4 |
Constraints
Time limit: 50 seconds
Memory limit: 512 MB
Output limit: 1 MB