Fişierul intrare/ieşire: | bila2.in, bila2.out | Sursă | Concurs IQ Academy clasa a 7-a |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 1 sec | Limită de memorie | 16384 kbytes |
Scorul tău | N/A | Dificultate |
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 ≤ L0 ≤ M
- 1 ≤ C0 ≤ N
- 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.in | bila2.out | Explicaţ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). |