Harta jocului PacmMan este sub forma unui dreptunghi împărțit în camere organizate pe linii și coloane. Din fiecare cameră se poate merge în camera situate pe coloana următoare și pe aceeași linie, sau in camera de pe coloana următoare și linia următoare, dar fără a ieși din hartă. Astfel din camera (i,j) se poate merge în camerele (i,j+1) și (i+1,j+1). PacMan se află în camera situată pe prima linie și pe prima coloana (1,1) și trebuie să ajungă în camera de pe ultima linie și ultima coloană (n,m). Calculați și afișați numărul de trasee pe care poate PacMan să parcurgă harta, folosind programarea dinamică
Răspunsuri la întrebare
Răspuns:
Cerinţa
Harta jocului PacmMan este sub forma unui dreptunghi împărțit în camere organizate pe linii și coloane. Din fiecare cameră se poate merge în camera situate pe coloana următoare și pe aceeași linie, sau in camera de pe coloana următoare și linia următoare, dar fără a ieși din hartă. Astfel din camera (i,j) se poate merge în camerele (i,j+1) și (i+1,j+1). PacMan se află în camera situată pe prima linie și pe prima coloana (1,1) și trebuie să ajungă în camera de pe ultima linie și ultima coloană (n,m). Calculați și afișați numărul de trasee pe care poate PacMan să parcurgă harta.
Date de intrare
Fișierul de intrare pacman_xi.in conține pe prima linie merele n și m, reprezentând numărul de linii și, respectiv, de coloane ale hărții.
Date de ieșire
Fișierul de ieșire pacman_xi.out va conține pe prima linie numărul s, reprezentând numărul de trasee pe care poate PacMan să parcurgă harta.
Restricții și precizări
1 ≤ n,m ≤ 40
Exemplu
pacman_xi.in
3 4
pacman_xi.out
3
Explicație
Cele 3 trasee sunt cele din imaginea de mai jos.
