Fişierul intrare/ieşire:bila2.in, bila2.outSursăConcurs IQ Academy clasa a 7-a
AutorDin FolclorAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Bila2 (clasa a 7-a)

Se dă o hartă, codificată sub forma unei matrice şi poziţia iniţială a unei bile. Fiecare valoare reţinută în matrice reprezintă înălţimea poziţiei respective. Se ştie că bila se poate rostogoli către o înălţime strict mai mică doar în poziţii învecinate pe direcţiile nord, sud, est şi vest. Se cere să se afişeze numărul de drumuri pe care le poate parcurge bila astfel încât să ajungă într-unul din colţurile matricei.

Date de intrare

Fişierul de intrare bila2.in conţine pe prima linie două numere naturale M şi N, reprezentând numărul de linii şi, respectiv, numărul de coloane ale matricei. Pe următoarele M linii se află câte N numere naturale nenule separate prin câte un spaţiu, reprezentând înălţimile asociate componentelor matricei. Pe cea de-a M+2 - a şi totodată ultima linie a fişierului se află coordonatele (L0, C0) iniţiale ale bilei.

Date de ieşire

In fişierul de ieşire bila2.out veţi scrie un singur număr, anume numărul de drumuri cerute. Deoarece acest număr este foarte mare el va fi afişat modulo 232.

Restricţii

  • 1 ≤ M, N ≤ 1000
  • 1 ≤ L0M
  • 1 ≤ C0N
  • Fiecare element al matricei va fi un număr natural nenul mai mic sau egal cu 1000.
  • În cazul în care din punctul de pornire nu se poate ajunge în niciun colţ al matricei, se va afişa 0, deoarece avem zero drumuri.
  • Numărul de drumuri se va afişa modulo 232.

Exemplu

bila2.inbila2.outExplicaţie
2 3
5 3 2
6 2 1
1 1
4
Matricea are 2 linii si 3 coloane. Pozitia de start este (1, 1).
Prin urmare un drum valid este (1, 1). Celelalte drumuri catre colturile matricei sunt:
(1, 1) (1, 2) (1, 3)
(1, 1) (1, 2) (1, 3) (2, 3)
(1, 1) (1, 2) (2, 2) (2, 3)
Coltul (2, 1) nu este accesibil din punctul de pornire (1, 1).
Trebuie sa te autentifici pentru a trimite solutii. Click aici