Complexitate timp: $O(NlogN)$.
Complexitate spatiu: $O(N)$.

h1(#Padure2). 'K. Padure2':problema/padure2
 
Se observa ca numarul de moduri prin care se poate ajunge din (i1,j1) in (i2,j2) fara a baga in seama obstacolele este
Combinari(n, k) unde n = (i2 – i1) + (j2-j1), iar k = (i2-i1).
Stiind acest lucru putem defini o functie f(i1, j1, i2, j2) care calculeaza numarul de moduri prin care se poate ajunge din (i1,j1) in (i2,j2) fara a baga in seama obstacolele.
Sortam punctele in functie de diagonala secundara.
Fie un vector nr[i] = numarul de moduri prin care se poate ajunge din (1,1) in (l[i], c[i]), fara a trece printr-un obstacol.
Recurentapentru acest vector v-a fi:
 
!onis-2016/solutii-runda-2?padure2_formula.png!
 
La final trebuie calculat dupa aceeasi regula pentru n,m.
 

h1(#Padure2). 'K. Padure2':problema/padure2