Labirintas (Lietuva)
Pažvelkite į labirintą, sudarytą iš lygiakraščių trikampių:

Kiekviena viršūnė apibūdinama dviem koordinatėmis x ir y, kaip parodyta paveiksle. Kai kurios kraštinės pažymėtos juodais arba baltais skrituliais. Per labirintą einama laikantis dviejų taisyklių: 
•	galima eiti tik kraštinėmis, pažymėtomis skrituliais.
•	negalima du kartus iš eilės eiti per kraštines su tos pačios spalvos skrituliais, t.y. galima eiti tik baltu skrituliu pažymėta kraštine, jei praeitu ėjimu buvo eita juodu skrituliu pažymėta kraštine, ir atvirkščiai. Pirmu ėjimu galima eiti ir baltu, ir juodu skrituliu pažymėta kraštine.
Užduotis
Parašykite programą, kuri rastų trumpiausio kelio nuo įėjimo iki išėjimo labirinte ilgį. Kelio ilgis yra apibrėžtas kaip praeitų kraštinių (arba skritulių) skaičius. Laikykite, jog toks kelias visuomet egzistuoja.
Pradiniai duomenys
Pradiniai duomenys pateikiami byloje MAZE.IN. Pirmoje eilutėje įrašyti du sveikieji skaičiai W ir H – atitinkamai labirinto plotis ir aukštis (1  W, H  500). Antroje eilutėje įrašyti keturi sveikieji skaičiai: X1 Y1 X2 Y2 (0  X1, X2  W; 0  Y1, Y2  H ). (X1, Y1) yra įėjimo į labirintą koordinatės, o (X2, Y2) – išėjimo koordinatės.
Tolesnėse 2H+1 eilučių pateikiamas kraštinių aprašymas: nelyginėse eilutėse (trečioje, penktoje, ir t.t.) aprašomos horizontalios kraštinės, o lyginėse eilutėse (ketvirtoje, šeštoje ir t.t.) aprašomos nehorizontalios kraštinės. Kiekviena eilutė susideda iš simbolių n, w ir b, kur n reiškia, jog kraštinė nepažymėta skrituliu, o w arba b reiškia, jog kraštinė pažymėta atitinkamai baltu arba juodu skrituliu. Tarp šių simbolių nėra tarpų. Nelyginės eilutės susideda iš lygiai W simbolių, o lyginės – iš lygiai 2W+1 simbolių.

Rezultatai
Pirmoje (ir vienintelėje) rezultatų bylos MAZE.OUT eilutėje programa turi išspausdinti vieną sveikąjį skaičių – trumpiausio kelio nuo įėjimo iki išėjimo labirinte ilgį.
pavyzdžiai
Pradiniai duomenys	Rezultatai	Komentaras	
2 1
0 0 2 1
bb
nwwnw
bn
	6
	Paprastas labirintas. Vienas iš trumpiausių kelių yra šis:
(0, 0)  (1, 0)  (0, 1)  (1, 1)  (1, 0) (2, 0)  (2, 1)
Labirinto ir trumpiausio kelio iliustracija:
	
Pradiniai duomenys	Rezultatai	Komentaras	
5 4
0 2 5 2
nnbnn
nnnwwbwnnnn
nbbbn
nnwbwwbwwnn
bwwww
nnbwbbwwbnn
nwwwn
nnnnbwbbnnn
nnwnn
	22
	Tai labirinto, pavaizduoto paveiksle pirmame užduoties lape, aprašymas. Trumpiausias kelias yra šis:
(0, 2)  (1, 2)  (1, 1)  (2, 1)  (2, 0)  (3, 0) 
(3, 1)  (3, 2)  (4, 1)  (3, 1)  (3, 0)  (2, 0) 
(2, 1)  (1, 1)  (1, 2)  (1, 3)  (2, 3)  (2, 4) 
(3, 4)  (3, 3)  (4, 3)  (4, 2)  (5, 2)
(Kelio ilgis: 22)