Fișierul intrare/ieșire drenaj.in, drenaj.out Sursă OMI Iasi 2011
Autor Emanuela Cerchez Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in drenaj.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii