Žaidimas 8

Pradinių duomenų failas:

zaidimas.in  

Rezultatų failas:

zaidimas.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Daugelis gerai žino žaidimą 15: 4×4 dydžio lentelėje atsitiktine tvarka surašyti skaičiai nuo 1 iki 15, o vienas langelis paliktas tuščias; į šį tuščią langelį galima „perstumti“ skaičių iš gretimo langelio (tuomet šis tampa tuščias). Žaidimo tikslas – sustumdyti skaičius taip, jog jie lentelėje būtų surašyti iš eilės, o tuščias liktų paskutinis langelis (taip, kaip parodyta paveiksle).

Žaidimas 8 – tai sumažintas žaidimo 15 variantas (žaidžiama 3×3 dydžio lentelėje). Parašykite programą, kuri rastų, kiek mažiausiai ėjimų pakanka duotam žaidimui laimėti, arba nustatytų, kad laimėti neįmanoma.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas žaidimų skaičius T (1 <= T <= 1000). Toliau seka T žaidimo aprašymų. Kiekvieną aprašymą sudaro trys eilutės, kuriose įrašyta po tris skaičius nuo 0 iki 8 (skaičiai viename žaidimo aprašyme nesikartoja – tai pradinis skaičių išdėstymas lentelėje). Skaičius 0 žymi tuščią langelį. Prieš kiekvieną žaidimo aprašymą įrašyta tuščia eilutė.

Rezultatai

Rezultatų failą turi sudaryti T eilučių. Kiekvienam žaidimo aprašymui, iš eilės, turi būti įrašytas mažiausias ėjimų skaičius, reikalingas tam žaidimui laimėti. Jei žaidimo laimėti neįmanoma, turi būti įrašytas -1.

Pavyzdžiai

3

1 2 3
5 7 6
0 4 8

1 3 5
4 2 6
0 7 8

3 4 5
1 8 2
0 7 6

6
8
12