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

...

Rezolvare 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.
 
Astfel, algoritmul va sorta crescător toate cele n2 pătrăţelele în funcţie de înălţime şi...
 
== 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ă:
	dacă lg[i][j] < lg[i’][j’] + 1 atunci
	  lg[i][j] = lg[i’][j’] + 1
	sfârşit(dacă)
    sfârşit(pentru)
  sfârşit(pentru)
 
   caută max{lg[i][j] : 1 <= i, j <= n}
  reconstruieşte drumul alegând un vecin cu lungimea mai mică cu exact 1
  până ce se ajunge la marginea matricei.
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)).
 
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.
În programul principal:
 
== code(cpp)  |
Algoritm Pietre(n,t): 	// n: dimensiunea tabloului t
  max = 0	// lungimea maximă a drumului }
  maxlin = 0 	// linia de unde porneşte cel mai lung drum }
  maxcol = 0	// coloana de unde porneşte cel mai lung drum }
  lin = 1 	// vom încerca să intrăm în tablou pornind din linia 1 }
  pentru col=1,n execută:
    maxnou = 0 	// maximul actual }
    rez[lin,col] = 1 	// marcăm punctul de pornire }
    cauta(lin,col,2) 	// căutăm un drum având acest punct de start }
    dacă maxnou > max atunci	// actualizarea }
      max = maxnou
      maxlin = lin
      maxcol = col
    sfârşit(dacă)
  sfârşit(pentru)
  //...  	 la fel procedăm cu linia n, coloana 1 şi coloana n
sfârşit(algoritm)
 
Algoritm Cauta(lin,col,pas):
  pentru i=1,4 execută:	{ un element are 4 vecini }
    lin_nou = lin + x[i] 	//{ indicele de linie al vecinului }
    col_nou = col + y[i]	//{ indicele de coloană }
	//{ dacă am generat o poziţie pe teren }
    dacă (lin_nou = {1,2,...,n}) şi (col_nou = {1,2,...,n}) atunci
      dacă rez[lin_nou,col_nou] = 0 atunci 	//{ dacă nu am fost aici }
	//{ dacă numărul pietrelor este cu 1 mai mare }
        dacă t[lin_nou,col_nou] = t[lin,col] + 1 atunci
          rez[lin_nou,col_nou] = pas	//{ facem pasul }
          dacă pas > maxnou atunci    	{ actualizăm maximul actual }
            maxnou = pas
          sfârşit(dacă)
          Cauta(lin_nou,col_nou,pas+1) 	{ încercăm să continuăm drumul }
          rez[lin_nou,col_nou] = 0	{ ştergem pasul, pentru că vom căuta alt drum }
        sfârşit(dacă)
      sfârşit(dacă)
    sfârşit(dacă)
  sfârşit(pentru)
Sfârşit(algoritm)
==
 
 
unde şirurile x şi y au valorile:
x = (-1,0,1,0)
y = (0,1,0,-1)