----------------------------------
| PROBLEMA 14: Alpinism |
| PUNCTAJ: 55 Dexteri |
| DEADLINE: Luni, 5 Aprilie |
| TIMP DE IMPLEMENTARE: 60 minute |
| TIMP DE EXECUTIE: 1 sec./ |
| Pentium 166 Mhz. |
----------------------------------
Imaginati-va ca sunteti un alpinist inrait. Vreti sa urcati, sa urcati, si
iar sa urcati. Pentru a va satisface setea de urcus, trebuie sa va selectati
un traseu pe care sa urcati cat mai mult timp.
Regiunea muntoasa in care va aflati este codificata sub forma unei matrici
patratice de ordinul n, fiecare element al matricii reprezentand altitudinea
respectivei portiuni de teren.
Traseul poate incepe din orice punct al regiunii (deci de la oricare dintre
elementele matricii) si poate avansa intr-un punct vecin la stanga, la dreapta,
in sus sau in jos (deci nu si pe diagonala) atata timp cat traseul urca (deci
altitudinea punctului curent este strict mai mica decat altitudinea punctului
urmator). Fiecare deplasare dureaza o unitate de timp.
Datele de intrare se citesc din fisierul "alpin.in" sub urmatorul format:
n
a11 a12 ...... a1n
a21 a22 ...... a2n
....
an1 an2 ...... ann
Datele de iesire sunt scrise in fisierul "alpin.out" sub
urmatorul format:
l - lungimea traseului parcurs
l1 c1 l2 c2 - (l1,c1) reprezinta coordonatele punctului de plecare,
iar (l2,c2) reprezinta coordonatele punctului de sosire.
Exemplu:
alpin.in alpin.out (o solutie posibila)
-------- ---------
6 15
29 10 8 9 8 10 4 3 4 4
22 11 7 3 7 20
17 15 3 14 45 30
19 5 2 41 19 17
23 8 90 39 20 18
27 30 32 35 70 19
|
|
