Fişierul intrare/ieşire:drenaj.in, drenaj.outSursăOMI Iasi 2011
AutorEmanuela CerchezAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Drenaj (clasa a 10-a)

Vasile şi-a cumpărat la munte o frumuseţe de teren. Din păcate, la prima ploaie a observat că anumite porţiuni de teren se inundă, terenul devenind mlăştinos. Pentru a rezolva problema trebuie să construiască un sistem de drenaj. Pentru aceasta, analizează harta terenului. Pe hartă, terenul este figurat ca o zonă dreptunghiulară împărţită în NxM pătrate aranjate pe N linii şi M coloane. În fiecare pătrat este specificată cota zonei de teren reprezentată.

Numim nivel o zonă formată din pătrate care au aceeaşi cotă, astfel încât oricum am alege două pătrate de pe nivel putem ajunge de la un pătrat la celălalt trecând numai prin pătrate situate pe acel nivel. Din orice pătrat ne putem deplasa la unul dintre vecinii săi (pătrate care au o latură comună cu pătratul respectiv).

Dacă un nivel are cel puţin un vecin cu cota strict mai mică decât a pătratelor de pe nivelul respectiv, atunci apa se va scurge în vecinul/vecinii cu cotă mai mică şi prin urmare, acel nivel nu se inundă. Dacă însă un nivel are ca vecini doar pătrate cu cote strict mai mari decât cota pătratelor de pe nivelul respectiv, el va fi inundat şi va trebui să construim pentru nivelul respectiv un canal de drenaj, canal care va evacua apa de pe întreg nivelul.

Cerinţă

Să se determine numărul minim de canale de drenaj care trebuie să fie construite pentru a evacua apa de pe întreg terenul.

Date de intrare

Fişierul de intrare drenaj.in conţine pe prima linie numere naturale N şi M separate prin spaţiu. Pe următoarele N linii sunt scrise câte M numere naturale separate prin spaţii reprezentând, în ordine, cotele din cele NxM pătrate care constituie terenul.

Date de ieşire

Fişierul de ieşire drenaj.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând numărul minim de canale de drenaj ce trebuie să fie construite pentru a evacua apa de pe teren.

Restricţii

  • 1 ≤ N, M ≤ 100
  • Cotele sunt numerele naturale ≤ 10000
  • Puteţi considera că terenul este înconjurat de zone cu cota 10001.

Exemplu

drenaj.indrenaj.outExplicaţii
6 5
1 1 2 1 1
1 1 1 1 2
6 6 6 1 2
2 2 2 2 2
4 1 4 4 4
1 4 4 3 3
4
Vor fi inundate cele 3 niveluri cu cota 1 şi nivelul cu cota 3,
deci trebuie să construim 4 canale de drenaj.
Trebuie sa te autentifici pentru a trimite solutii. Click aici