Fișierul intrare/ieșire | drenaj.in, drenaj.out | Sursă | OMI Iasi 2011 |
---|---|---|---|
Autor | Emanuela Cerchez | Adăugată de |
|
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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. |