Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_1995_3e2_trump_kelias.in

Rezultatų failas: lmio_1995_3e2_trump_kelias.out

Jei norite pateikti savo sprendimą - prisijunkite.

Trumpiausias kelias

Duotas stačiakampis laukas, kurio kampų koordinatės yra (0,0) ir (100,100). Jo viduje išdėstyta n kvadratėlių:

< insert image here >

Be to, žinoma, kad kiekvieno kvadratėlio kraštinės ilgis yra 5 vienetai; kvadratėlių kraštinės yra lygiagrečios koordinačių ašims; kvadratėlių kampų koordinatės – sveikieji skaičiai; kvadratėliai vienas nuo kito atskirti bent vienu vienetu.

Užduotis

Reikia rasti trumpiausią kelią iš taško (0,0) į (100,100) tokį, kuris nekirstų kvadratėlių.

Pradiniai duomenys

Pirmoje eilutėje yra kvadratėlių skaičius n. Kitose eilutėse yra kvadratėlių apatinių kairiųjų kampų koordinatės x ir y.

Rezultatai

Rezultatai – kelio koordinatės – turi būti rašomi vienoje eilutėje po vieną koordinatę. Turi būti pradinė kelio koordinatė, po to koordinatės, kuriose kelias keičia savo kryptį, ir galinė kelio koordinatė. Koordinatės turi būti rašomos ta tvarka, kuria jos išsidėstę kelyje.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
5 5
5 15
15 10
15 20
90 90
 
  0   0
  5  10
 20  20
 95  90
100 100

Ribojimai

n\\leq30

0\\leqx\\leq95

0\\leqy\\leq95