Laiko ribojimas: 1s

Atminties ribojimas: 16MB

Jei norite pateikti savo sprendimą - prisijunkite.

Rikis

N\\timesN 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).

board

Pradiniai duomenys

Pirmoje pradinių duomenų failo eilutėje įrašytas skaičius N (8\\leN\\le100). 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