- Pradinių duomenų failas:
- rikis.in
- Rezultatų failas:
- rikis.out
- Laiko apribojimas:
- 1 s.
- Atminties apribojimas:
- 16 Mb.
Užduotis
N x N dydžio šachmatų lentoje stovi rikis ir valdovė. Rikis turi pasiekti langelį, kuriame stovi valdovė. Tačiau kai kurie šachmatų lentos langeliai yra išpjauti ir per juos eiti rikis negali (išpjauti langeliai paveiksle pažymėti kryžiuku).
Primename, kad rikis gali vaikščioti tik įstrižai, t. y. ant juodo langelio stovintis rikis gali vaikščioti tik juodais, o ant balto – tik baltais langeliais. Įstrižai vienu ėjimu rikis gali paeiti per kelis langelius nekeisdamas ėjimo krypties (tik negali eiti į išpjautą langelį ar jį peršokti). Paveiksle parodytas rikis ir pažymėti visi langeliai, kuriuos jis gali pasiekti VIENU ėjimu.
Parašykite programą, kuri nustatytų, kiek mažiausiai ėjimų reikės padaryti rikiui, kad jis patektų į langelį, kuriame stovi valdovė (ši nejuda).
Pradiniai duomenys
Pirmoje pradinių duomenų failo eilutėje įrašytas skaičius N (8 <= N <= 100). Toliau seka N eilučių po N simbolių, kurie vaizduoja šachmatų lentą. Simboliu „0“ žymimas neišpjautas lentos langelis, simboliu „1“ – išpjautas lentos langelis, simboliu „R“ – rikio pozicija, simboliu „V“ – valdovės pozicija.
Pastaba: valdovės ir rikio pradinės pozicijos visada skirtingos.
Rezultatai
Rezultatą – vieną sveikąjį teigiamą skaičių – reikia įrašyti į pirmąją ir vienintelę rezultatų failo eilutę. Tai mažiausias skaičius ėjimų, kuriuos teks padaryti rikiui, kad patektų į langelį, kuriame stovi valdovė. Jeigu rikis pas valdovę patekti negali, įrašykite 0.
Pavyzdžiai
Pradiniai duomenys | Rezultatai |
---|---|
8 00000000 0R000000 00100000 000V0000 00000000 00000000 00000000 00000000 |
3 |
8 00000000 0R000000 11111111 000V0000 00000000 00000000 00000000 00000000 |
0 |