| Fişierul intrare/ieşire: | zoro.in, zoro.out | Sursă | Algoritmiada 2018 Runda PreOJI |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.45 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zoro
Zoro se afla pe o insula reprezentata printr-o matrice cu N linii si M coloanea, fiecare celula din matrice avand o valoare data. Scopul lui Zoro este ca pornind din celula (1,1) sa ajunga in celula (N, M) (unde se poate bate cu legendarul pirat Mihawk).
Deoarece insula este foarte periculoasa, Zoro se simte nevoit sa isi foloseasca instinctele de orientare. Astfel, acesta a realizat ca dintr-o celula (x1, y1) se poate muta intr-o alta celula (x2, y2) doar daca:
- Valoarea acesteia este strict mai mica decat cea in care se afla (val[x1][y1] > val[x2][y2])
- Noua celula se afla pe aceeasi linie sau coloana ( x1 = x2 sau y1 = y2)
Toata lumea stie ca orientarea nu este punctul forte al lui Zoro. Ca urmare, dandu-se N, M si matricea cu N linii si M coloane, aflati care este cel mai lung drum care porneste din celula (1, 1) si ajunge in (N, M).
Date de intrare
Fişierul de intrare zoro.in va contine pe prima linie 2 numere naturale N si M. Pe urmatoarele N linii se afla cate M numere reprezentand valorile matricei.
Date de ieşire
Fişierul de ieşire zoro.out va contine un singur numar natural reprezentand distanta maxima pe care o poate parcurge Zoro din celula (1, 1) pana in celula (N, M)
Restricţii
- 1 ≤ N, M ≤ 1.000
- Valorile din matrice sunt numere naturale distincte din intervalul [1, N * M].
- Se garanteaza ca exista cel putin un drum valid.
- Veţi primi rezultatele evaluării doar pe fişierele de intrare din exemplu. Acestea nu vor afecta scorul problemei, având punctajul asociat 0.
Exemplu
| zoro.in | zoro.out |
|---|---|
| 3 3 7 4 2 9 8 3 6 5 1 | 6 |
Explicaţie
Cel mai lung drum trece prin 6 celule: (1, 1) - (3, 1) - (3, 2) - (1, 2) - (1, 3) - (3, 3).
