Tsunamiul este valul mareic ce se propagă prin apa oceanelor/mărilor, ca urmare a producerii unor erupţii subacvatice sau/şi a unor cutremure submarine sau de coastă foarte puternice.
Cercetătorii doresc să preîntâmpine efectele unor posibile valuri mareice prin marcarea şi clasificarea zonelor al căror risc de inundare este ridicat.
Teritoriul studiat a fost împărţit în n×m pătrate identice (zone) rezultând o hartă digitizată, reprezentată sub forma unui tablou bidimensional cu n linii şi m coloane, fiecare element al tabloului memorând cota (înălţimea) terenului din pătratul unitate corespunzător. Zonele de apă au cota 0, iar zonele de uscat au cote mai mari decât 0.
Orice tsunami este clasificat în funcţie de înălţimea valului mareic, pe o scară de la 1 la 10. Cercetătorii doresc să marcheze zonele de risc ce pot fi afectate de un potenţial tsunami.
Iniţial, valul mareic apare în toate zonele de cotă 0 vecine cu cel puţin o zonă de uscat. O zonă teritorială poate fi afectată dacă are cota strict mai mică decât înălţimea valului mareic şi se află în vecinătatea apei sau în vecinătatea unei zone afectate. Două pătrate unitate se învecinează dacă au o latură comună.

Cerinţă

Dată fiind harta digitizată a zonelor monitorizate, să se determine numărul zonelor de uscat afectate de un tsunami de înălţime h.

Date de intrare

Fişierul de intrare tsunami.in conţine pe prima linie trei numere naturale n m h separate prin câte un spaţiu, reprezentând dimensiunile hărţii, respectiv înălţimea valului mareic. Pe următoarele n linii sunt scrise câte m numere naturale separate prin câte un spaţiu reprezentând, în ordine, cotele din cele n×m pătrate teritoriale unitate ale hărţii.

Date de ieşire

Fişierul de ieşire tsunami.out conţine o singură valoare ce reprezintă numărul pătratelor unitate afectate de un tsunami de înălţime h.

Restricţii

• 2 ≤ n, m ≤ 1000
• 1 ≤ h ≤ 10
• Zona monitorizată nu conţine lacuri interioare (pătrate unitate învecinate, având cota 0, înconjurate complet de pătrate unitate având cote strict mai mari decât 0)
• Cotele sunt numere naturale ≤ 1000.

Exemple

tsunami.in	tsunami.out
6 7 3 0 0 4 2 5 0 0 1 0 0 7 3 6 0 2 3 0 5 2 2 0 0 7 5 4 0 0 0 0 5 2 3 0 2 0 0 4 4 8 0 2 0	6

autor: Prof. Eugen Nodea

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com