- Pradinių duomenų failas:
- musis.in
- Rezultatų failas:
- musis.out
- Laiko apribojimas:
- 1 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
Kvadratinėje šachmatų tipo lentoje įvyko mūšis. Po mūšio lentoje liko keletas raitininkų ir vienas sužeistas karalius. Tame pačiame lentos langelyje gali stovėti keletas figūrų ir jos juda viena kitai netrukdydamos – taip tarsi būtų vienos lentoje. Kai kurie lentos langeliai yra užimti priešo. Nei raitininkų, nei karaliaus šiuose langeliuose nėra, ir jiems ten patekti negalima.
Raitininkas vienu ėjimu lentoje gali persikelti du langelius horizontaliai ir vieną vertikaliai arba du langelius vertikaliai ir vieną horizontaliai (t.y. raitininko ėjimai yra įprasti šachmatų žirgo ėjimai, jie pavaizduoti paveiksle dešinėje). Langeliai, esantys tarp pradinės ir galutinės raitininko ėjimo pozicijos, gali būti užimti priešo – raitininkas šiuos langelius peršoka.
Karalius yra sužeistas ir pats judėti negali, bet karalių gali nešti raitininkas. Tai vyksta taip: į karaliaus langelį atėjus raitininkui, karalius su raitininku sėdasi ant raitininko žirgo ir tolimesniuose ėjimuose ši pora juda kaip viena raitininko figūra. Jei karaliaus langelyje iš karto yra vienas ar keli raitininkai, tai karalius prisijungia prie bet kurio iš jų.
Karalius nori kuo greičiau kartu su visais raitininkais susirinkti viename lentos langelyje. Parašykite programą, kuri rastų, po kiek mažiausiai ėjimų visos figūros susirinks viename lentos langelyje. Vienu ėjimu pajuda tik viena figūra – raitininkas (su karaliumi ar be jo).
Pradiniai duomenys
Pirmoje pradinių duomenų failo eilutėje įrašyti trys tarpu atskirti sveikieji skaičiai: M, R ir P. Čia M (1 <= M <= 100) – eilučių ir stulpelių skaičius lentoje, R (0 <= R <= 100) – raitininkų skaičius, P(0 <= P < M2) – priešo langelių skaičius.
Antroje eilutėje įrašytos pradinės karaliaus koordinatės. Tolesnėse R eilučių įrašytos raitininkų koordinatės. Toliau jų seka P eilučių, kurių kiekvienoje įrašytos priešo langelio koordinatės. Koordinatės užrašomos kaip du tarpu atskirti sveikieji skaičiai – eilutės ir stulpelio numeris.
Rezultatai
Į pirmą ir vienintelę rezultatų failo eilutę įrašykite atsakymą – mažiausią ėjimų skaičių, per kurį visos figūros gali susirinkti viename lentos langelyje, skaičius. Jei visos figūros iš karto stovi tame pačiame langelyje, tai ėjimų skaičius lygus 0. Jei visos figūros susirinkti viename langelyje negali, tai į rezultatų bylą reikia įrašyti -1.
Pavyzdžiai
| Pradiniai duomenys | Rezultatai | Paaiškinimas |
|---|---|---|
7 3 1 2 3 4 2 6 5 5 6 4 4 |
5 |
 |
4 2 0 1 1 1 1 1 1 |
0 |