Nosaukums
Šaha tornis (tornis)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
100%

Definīcija

Uz kvadrātiskas rūtiņu lapas, kurai dažas rūtiņas var būt izgrieztas, novietota šaha figūra - tornis.
Tornis vienā gājienā var pārvietoties uz jebkuru citu neizgrieztu lapas rūtiņu, kas ar sākotnējo atrodas vienā rindā vai kolonnā.
Tornis nedrīkst pārvietoties pāri izgrieztai rūtiņai.
Zīmējumā redzams, uz kurām rūtiņām tornis drīkst pārvietoties, ja pirms gājiena tas atrodas rūtiņā ar koordinātām (2;6).

Noskaidrot ar kādu mazāko gājienu skaitu tornis no sākotnējās rūtiņas var nokļūt līdz norādītai rūtiņai (ja tas vispār ir iespējams), pārvietojoties saskaņā ar iepriekšaprakstītajiem noteikumiem.


Ievaddatu raksturojums

Ievaddatu pirmajā rindiņā ir trīs naturāli skaitļi n, x un y (1<=n<=100, 1<=x, y<=n).
Skaitlis n ir kvadrātiskās rūtiņu lapas malas izmērs, bet x, y - tās rūtiņas koordinātes, uz kuru jānokļūst tornim. Zināms, ka rūtiņa (x,y) nav izgriezta.
Faila otrajā rindiņā ir viens skaitlis k (0<=k<=1000) - izgriezto rūtiņu skaits.
Nākamajās k faila rindiņās ir skaitļu pāri xi, yi - i-tās izgrieztās rūtiņas koordinātes.
Pieņemt, ka sākotnēji tornis atrodas rūtiņā ar koordinātēm (1,1), kas nav izgriezta.


Izvaddatu raksturojums

Izvaddatos jāizvada viens skaitlis - mazākais gājienu skaits, kurā tornis no sākotnējās pozīcijas var nokļūt līdz mērķim.
Ja tornis nevar nokļūt līdz mērķim, tad jādrukā atbilde - NEVAR.


Piezīmes

Uzdevums izmantots Latvijas 15.informātikas olimpiādes I (skolas) kārtā.
Autori: M.Opmanis, A.Žogla


Paraugdati

Stdin
4 1 4
3
1 3
4 1
3 4
Stdout
3

Stdin
2 2 2	
2
1 2
2 1
Stdout
NEVAR

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.