Fișierul intrare/ieșire bila2.in, bila2.out Sursă Concurs IQ Academy clasa a 7-a
Autor din folclor Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.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).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii