Fişierul intrare/ieşire:zoro.in, zoro.outSursăAlgoritmiada 2018 Runda PreOJI
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.9 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.inzoro.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).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?