h2(#pietre2). 'Pietre2':problema/pietre2

Rezolvare 1

*Soluţie $1$*

Soluţia se bazează pe observaţia că dacă vom procesa înălţimile în ordine crescătoare, atunci vom putea actualiza un drum de lungime maximă ce se termină în fiecare din aceste pătrăţele în mod corect.

Rezolvarea se bazează pe observaţia că dacă vom procesa înălţimile în ordine crescătoare, atunci vom putea actualiza un drum de lungime maximă ce se termină în fiecare din aceste pătrăţele în mod corect.

Astfel, algoritmul va sorta crescător toate cele n2 pătrăţelele în funcţie de înălţime şi...

Astfel, algoritmul va sorta crescător toate cele $n^2^$ pătrăţelele :

== code(cpp)|

== code(cpp) |

Algoritm Rezolvă(n):
  pentru fiecare (h, i, j) execută:	// pătrăţelul (i, j) cu înălţimea h
    pentru fiecare vecin (h’, i’, j’) cu h = h’ + 1 execută:

Sfârşit(algoritm)
==

În implementare se va ţine cont ca pătrăţelele de pe marginea matricei care sunt puncte de plecare să fie marcate iniţial cu 0.
Complexitate: O(N^2^ log(N)).

În implementare se va ţine cont ca pătrăţelele de pe marginea matricei care sunt puncte de plecare să fie marcate iniţial cu $0$.
Complexitate: $O(N^2^ log(N))$.

Rezolvare 2
Problema, în ciuda faptului că limita pentru n este mare, se putea aborda şi cu backtracking. Cu o rezolvare asemănătoare cu cea de mai jos se putea obţine 90 puncte.

*Soluţie $2$*
 
Problema, în ciuda faptului că limita pentru n este mare, se putea aborda şi cu backtracking. Cu o rezolvare asemănătoare cu cea de mai jos se putea obţine $90$ puncte.

În programul principal:
== code(cpp)  |

==

unde şirurile x şi y au valorile:
x = (-1,0,1,0)
y = (0,1,0,-1)

unde şirurile $x$ şi $y$ au valorile:
$x = (-1,0,1,0)$
$y = (0,1,0,-1)$
 
*Soluţie 3*
Problema se poate rezolva şi în complexitatea $O(N^2^)$ folosind memoizarea. Astfel, vom calcula pentru fiecare element al matricii cât se poate urca dacă pornim din elementul respectiv. Pseudocodul funcţiei care calculează pentru fiecare element cât se poate urca dacă pornim din elementul respectiv arată astfel:
 
== code(cpp) |
funcţie din(i, j):
  dacă(D[i][j] != 0) atunci
    returnează D[i][j]
  sfârşit dacă
 
  D[i][j] = 1
 
  pentru fiecare vecin (i’, j’) al perechii (i, j) execută:
    dacă A[i][j] + 1 = A[i’][j’] şi D[i][j] < din(i’, j’) + 1 atunci
      D[i][j] = din(i’, j’) + 1
    sfârşit dacă
  sfârşit pentru
Sfârşit(din)
==
 
Se observă că fiecare pentru fiecare element al matricii, funcţia este apelată de un număr constant de ori, deci complexitatea algoritmului este $O(N^2^)$.