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

Definīcija

Uz bezgalīgas rūtiņu lapas, kurai dažas rūtiņas var būt izgrieztas, novietota šaha figūra - tornis. Lapas rindas un kolonnas ir sanumurētas pēc kārtas ar veseliem skaitļiem. Kolonnas ir numurētas no kreisās puses uz labo, bet rindas no lejas uz augšu. 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 četras lapas rūtiņas ir izgrieztas un tornis pirms gājiena atrodas rūtiņā ar koordinātām (1;-1). Kā redzams, šajā gadījumā tornis var pārvietoties bezgalīgi tālu horizontālā virzienā pa kreisi vai vertikālā virzienā uz leju. Noskaidrot, ar kādu mazāko gājienu skaitu tornis no vienas norādītas rūtiņas var nokļūt līdz otrai 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 doti četri veseli skaitļi x1, y1, x2, y2, kas atdalīti ar tukšumsimboliem. x1 (kolonnas numurs) un y1 (rindas numurs) norāda tās rūtiņas koordinātes, kurā tornis atrodas sākumā, bet x2 un y2 analoģiskā veidā norāda tās rūtiņas numuru, kurā tornim jānokļūst beigās. Zināms, ka -109<=x1, y1, x2, y2 <= 109 un ka neviena no šīm divām rūtiņām nav izgriezta. Faila otrajā rindā dots naturāls skaitlis n - izgriezto rūtiņu skaits (n<=1000). Faila nākošajās n rindās katrā doti divi veseli skaitļi, kas atdalīti ar tukšumsimbolu - vienas izgrieztās rūtiņas koordinātas. Faila i+2-ajā rindā (1<=i<=n) ir dots i-tās izgrieztās rūtiņas kolonnas numurs p1 (-109<= p1<= 109) un rindas numurs q1(-109<= q1 <=109). 


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada viens vesels skaitlis - mazākais gājienu skaits, kurā tornis no vienas norādītas rūtiņas var nokļūt līdz otrai norādītai rūtiņai. Ja tornis nevar nokļūt līdz otrai norādītajai rūtiņai, tad faila vienīgajā rindā jāizvada vārds "NEVAR".


Piezīmes

Uzdevums izmantots Latvijas 15.informātikas olimpiādes III (Valsts) kārtā. 

Autors: M.Opmanis


Paraugdati

Stdin
1 -1 5 -4
4
1 1
5 -5
2 -4
4 -1
Stdout
3

Stdin
10 11 5001 -4733
5
5001 -4732
5001 -4734
1 1
5000 -4733
5002 -4733
Stdout
NEVAR

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