Un alpinist ar vrea să cucerească un vârf cât mai înalt din Munţii Carpaţi. Din păcate îi este frică să urce de pe o stâncă pe alta alăturată, dacă diferenţa de altitudine depăşeşte 100 de metri. În schimb el coboară fără frică de pe o stâncă pe alta alăturată, indiferent de diferenţa de altitudine.
Alpinistul are harta muntelui pe care vrea să-l escaladeze. Harta este codificată sub forma unui caroiaj în care în pătrăţele sunt notate altitudinile punctelor (înălţimile stâncilor) de pe hartă, date în metri faţă de nivelul mării. Alpinistul poate porni din orice pătrăţel de pe hartă cu altitudine 0 (aflat la nivelul mării) şi poate efectua un pas doar într-o porţiune de teren corespunzătoare unui pătrăţel de pe hartă, învecinat pe verticală sau pe orizontală cu pătrăţelul în care se află, cu condiţia să nu îi fie frică.

Cerinţă

Alpinistul apelează la ajutorul vostru pentru a afla traseul de lungime minimă pe care trebuie să-l urmeze pentru a escalada un vârf cât mai înalt.

Date de intrare

Fişierul de intrare alpinist.in conţine pe prima linie două numere naturale nenule M N, separate printr-un spaţiu, reprezentând dimensiunile caroiajului corespunzător hărţii. Pe următoarele M linii sunt scrise câte N numere naturale, separate prin câte un spaţiu, reprezentând valorile asociate caroiajului care codifică harta (linie după linie).

Date de ieşire

Fişierul de ieşire alpinist .out va conţine pe prima linie un număr natural ce reprezintă înălţimea maximă la care poate ajunge alpinistul. Pe linia a doua se vor scrie patru numere naturale nenule XP YP XD YD, separate prin câte un spaţiu, reprezentând coordonatele pătrăţelului din care pleacă alpinistul şi coordonatele pătrăţelului având înălţimea maximă în care poate ajunge; prin coordonatele pătrăţelului se înţeleg numărul liniei şi cel al coloanei pe care se află pătrăţelul în caroiaj. Pe a treia linie se va scrie un număr natural L reprezentând lungimea drumului; lungimea unui drum se defineşte ca fiind egal cu numărul pătrăţelelor străbătute de alpinist. Pe a patra linie se vor scrie L caractere, separate prin câte un spaţiu, reprezentând direcţia în care se mişcă alpinistul la fiecare pas i, i = 1, 2, …, L; caracterele pot fi: ′N′– corespunzător unei mişcări în sus, ′S′– corespunzător unei mişcări în jos, ′W′– corespunzător unei mişcări la stânga, ′E′– corespunzător unei mişcări la dreapta.

Restricţii

• 2 ≤ M, N ≤ 100
• 0 ≤ vi ≤ 1000, i =1,2,…,N (pe fiecare dintre cele M linii)
• dacă sunt mai multe drumuri de lungime minimă, în fişier se va scrie unul singur.

Exemple

alpinist.in	alpinist.out
3 5 0 101 2 14 100 50 149 149 250 200 0 100 10 400 10	250 3 1 2 4 8 E N E N E E S W

autor: Mihai Stroe

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com