Šaha tornis - 2

ID: tornis2
Grūtība: 4/5
Laika limits: 1

Uzdevums

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.

 

Ievaddati

Faila tornis2.in 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).

 

Izvaddati

Failā tornis2.out 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".

 

Piemērs

tornis2.intornis2.out
1 -1 5 -4
4
1 1
5 -5
2 -4
4 -1
3
  
tornis2.intornis2.out
10 11 5001 -4733
5
5001 -4732
5001 -4734
1 1
5000 -4733
5002 -4733
NEVAR

 

Atsauces

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

© 2001-2002 olimps! http://www.lio.lv/olimps/