== include(page="template/taskheader" task_id="game1") ==

Aceasta problema are dificultate medie.
 

Doi jucători joacă următorul joc:
Ei au o tablă de (M + 1) x (N + 1) celule. Pe linia M + 1 şi pe coloana N + 1 se regăsesc valori pozitive.
În colţul din stânga sus al tablei, celula (1, 1), se află un jeton pe care cei doi îl mută alternativ. O mutare constă în deplasarea jetonului în jos sau în dreapta. Mai formal, din celula (i, j) jetonul se poate muta în celula (i + 1, j) sau (i, j + 1).

Dacă jetonul ajunge pe ultima linie sau pe ultima coloană jocul se termină şi jucătorul 1 câştigă un număr de puncte egal cu valoarea aflată în celula în care a ajuns jetonul.

Dacă jetonul ajunge pe ultima linie sau pe ultima coloană, jocul se termină şi jucătorul 1 câştigă un număr de puncte egal cu valoarea aflată în celula în care a ajuns jetonul.

Prima mutare este efectuată de jucăţorul 1.
Considerând că amândoi jucătorii joacă perfect, care este câştigul maxim pe care îl poate câştiga primul jucătorul 1 ?

h2. Exemplu
table(example). |_. game1.in |_. game1.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2 2
  2 1
  3 4
| 3

|
h3. Explicaţie

...

Matricea arată în felul următor:
 
X . 3
. . 4
2 1 0
 
X reprezintă jetonul, iar . reprezintă o celulă goală.
Jucătorul unu va muta jetonul către dreapta ajungându-se la starea:
 
. X 3
. . 4
2 1 0
 
Jucătorul 2 poate muta în celula cu valoare 3 terminând jocul cu scorul 3, sau poate muta în jos, urmând ca jucătorul 1 să mute în dreapta terminând jocul cu scorul 4. Cum ambii jucători joacă perfect jucătorul 2 va alege varianta care îi minimează pierderea deci va termina jocul cu scorul 3.

== include(page="template/taskfooter" task_id="game1") ==