ID προβλήματος: turns3x3
Τίτλος: Στροφές 3x3
Βαθμός Δυσκολίας: 6
Ημερομηνία Εισαγωγής: 2000-06-05
Σχόλια:
Στροφές 3x3

Στο παιχνίδι αυτό έχουμε ένα πίνακα 3x3 o οποίος περιέχει τους αριθμούς 1 εώς 9. Ενδέχεται αυτοί να βρίσκονται όπως φαίνεται στο σχήμα: 

+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
Η παραπάνω κατάσταση του πίνακα ονομάζεται "ταξινομημένη". Οι επιτρεπόμενες "κινήσεις" που μπορούμε να κάνουμε σε μια οποιαδήποτε κατάσταση του πίνακα είναι η δεξιά ή αριστερή στροφή κατά 90 μοίρες ενός από τους 4 υποπίνακες 2x2 του πίνακα. Ο κάθε υποπίνακας 2x2 εδώ νοείται μόνο όταν τα στοιχεία του είναι διπλανά στον αρχικό πίνακα 3x3. Έτσι πχ. με στροφή του κάτω-δεξιά υποπίνακα δεξιά κατα 90 μοίρες, προκύπτει ο πίνακας: 
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 4 | 8 | 5 |
+---+---+---+
| 7 | 9 | 6 |
+---+---+---+
Η στροφή κατά 180 μοίρες θεωρείται 2 κινήσεις.

Αποδεικνύεται ότι με τις κινήσεις αυτές μπορούμε να φέρουμε τα στοιχεία του πίνακα 3x3 σε οποιαδήποτε μετάθεση.

Είσοδος: Στην είσοδο θα βρίσκονται εννιάδες αριθμών που θα δίνουν την αρχική κατάσταση του πίνακα. Οι αριθμοί θα χωρίζονται μεταξύ τους με απροσδιόριστο αριθμών κενών, tabs ή αλλαγών γραμμής. Η εννιάδα a b c d e f g h i συμβολίζει τον πίνακα 

+---+---+---+
| a | b | c |
+---+---+---+
| d | e | f |
+---+---+---+
| g | h | i |
+---+---+---+
Η είσοδος τελειώνει όταν δεν υπάρχουν άλλοι αριθμοί (μπορεί όμως να υπάρχουν κενά, tabs, αλλαγές γραμμής πριν το τέλος του αρχείου).

Εξοδος: Για κάθε εννιάδα της εισόδου θα δίνεται σε μια γραμμή ο μικρότερος αριθμός κινήσεων που χρειάζεται για να μετατραπεί η δοσμένη μορφή του πίνακα στην "ταξινομημένη" κατάσταση του πρώτου πίνακα.

Παραδείγματα εισόδου/εξόδου
ΕίσοδοςΈξοδος 
1 2 3
4 8 5
7 9 6

1
  2
    3
      4 5 6

7 9 8

1
5