Žaidimas su ratais

Pradinių duomenų failas:

ratai.in  

Rezultatų failas:

ratai.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

Šiame uždavinyje nagrinėsime žaidimą, žaidžiamą su keturiais ratais. Ant kiekvieno iš šių ratų pagal laikrodžio rodyklę surašyti skaitmenys nuo 0 iki 9. Viršutiniai keturi skaitmenys sudaro keturių skaitmenų sveiką skaičių. Pavyzdžiui, žemiau pateiktame paveiksle ratai sudaro skaičių 8056. Su kiekvienu ratu susieti du mygtukai. Paspaudus mygtuką, pažymėtą rodykle kairėn, atitinkamas ratas pasukamas per vieną skaitmenį pagal laikrodžio rodyklę, o paspaudus mygtuką, pažymėtą rodykle dešinėn – priešinga kryptimi.

Žaidimas pradedamas su tam tikra pradine ratų padėtimi. Tarkime, pradinė padėtis sudaro skaičių \(S_{1}\)\(S_{2}\)\(S_{3}\)\(S_{4}\). Jums duota kažkiek (tarkime, n) uždraustų padėčių \(F_{i1}\)\(F_{i2}\)\(F_{i3}\)\(F_{i4}\) (1 <= i <= n) ir galinė padėtis \(T_{1}\)\(T_{2}\)\(T_{3}\)\(T_{4}\). Parašykite programą, kuri rastų, kiek mažiausiai mygtukų paspaudimų pakaktų pradinę padėtį paversti galine, nesudarant nei vienos iš uždraustų padėčių.

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašyti keturi skaitmenys, atskirti tarpais – pradinė padėtis. Antroje eilutėje tokiu pačiu formatu pateikiama galinė padėtis.

Tolesnėje eilutėje įrašytas uždraustų padėčių skaičius n. Sekančiose n eilučių surašytos n uždraustų padėčių. Nei viena uždrausta padėtis nesutampa su pradine padėtimi.

Rezultatai

Į rezultatų failą jūsų programa turi įrašyti vienintelį sveiką skaičių – mažiausią reikalingą mygtukų paspaudimų skaičių, reikalingą galinei padėčiai pasiekti. Jei galinės padėties pasiekti neįmanoma, programa turi išvesti -1.

Pavyzdžiai

8 0 5 6
6 5 0 8
5
8 0 5 7
8 0 4 7
5 5 0 8
7 5 0 8
6 4 0 8

14

0 0 0 0
5 3 1 7
8
0 0 0 1
0 0 0 9
0 0 1 0
0 0 9 0
0 1 0 0
0 9 0 0
1 0 0 0
9 0 0 0

-1