Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Žaidimas su ratais

Š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.

ratai

Žaidimas pradedamas su tam tikra pradine ratų padėtimi. Tarkime, pradinė padėtis sudaro skaičių S_1S_2S_3S_4. Jums duota kažkiek (tarkime, n) uždraustų padėčių F_{i1}F_{i2}F_{i3}F_{i4} (1\\lei\\len) ir galinė padėtis T_1T_2T_3T_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

Pradiniai duomenys Rezultatai 
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