Tema 2, clasele 9-10, anul 2013-2014

Problema Pion este simplă ca idee, dar puțin mai dificilă ca implementare din cauza memoriei limitate.

Să presupunem că dorim sa aflăm mutarea optimă de la coordonatele (i, j) și că știm deja mutările optime și scorurile optime de la coordonate situate la est sau sud de (i, j). Atunci jucătorul 1 va muta în direcția care maximizează scorul, iar jucătorul 2 în direcția care minimizează scorul. Cum știm cine este la mutare? Bazat pe paritate. Jucătorul 1 va fi întotdeauna la mutare în punctele pentru care i + j este par, iar jucătorul 2 va fi întotdeauna la mutare în punctele pentru care i + j este impar.

Cu aceste informații putem completa o matrice S unde S(i, j) este scorul optim la care se va ajunge pornind de la (i, j).

$S(i,j)={\begin{cases}A(i,j),&{\mbox{dacă }}i=m+1{\mbox{ sau }}j=n+1\\\max(S(i+1,j),S(i,j+1)),&{\mbox{dacă }}i+j{\mbox{ este par}}\\\min(S(i+1,j),S(i,j+1)),&{\mbox{dacă }}i+j{\mbox{ este impar}}\end{cases}}$

De aici, era nevoie doar să implementați artificiul predat la cerc, cu care putem reduce consumul de memorie de la $O(mn)$ la $O(n{\sqrt {m}})$.