.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » drenaj

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
drenaj


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
2MB / 1MB

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.

Exemple

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.

autor: Prof. Emanuela Cerchez
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
De la OMI Iaşi 2011: rachete, pin, izvor, canguri, teme, numar4, alfabetar, cuvinte2, minmax, sumacifre, jocprim
De acelaşi autor: celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, oras, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre fill: rebus, sarpe, insule, lacuri, zuzu, joc11, gradina, dreptunghiuri, fillmat, parcela, acces, tsunami, betasah, zona, zone, taxa, foto, ferma1, antitero, robotzi
Software recomandat
surse trimise | ajutor