Fişierul intrare/ieşire: | mostenire2.in, mostenire2.out | Sursă | Concursul Naţional de Informatică Urmaşii lui Moisil 2017 |
Autor | Cosmin-Mihai Tutunaru | Adăugată de | |
Timp execuţie pe test | 0.15 sec | Limită de memorie | 128000 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Mostenire2
Fibocel tocmai a moştenit o pădure gigantică de formă dreptunghiulară pe care vrea să o transforme într-un parc de distracţii pentru copii. Cum îşi dă seama că este foarte mult de lucru şi nu ştie de unde să înceapă, s-a decis ca mai întâi să numere câte pădurici se află în pădurea moştenită. O pădurice este o suprafaţă dreptunghiulară înconjurată în totalitate de copaci, cu cel puţin o poieniţă oriunde în interior. O poieniţă este o suprafaţă fără copaci. Cum Fibocel şi-a dat seama că şi acest lucru este dificil de realizat, s-a decis să vă ceară vouă ajutorul!
Cerinţă
Dându-se padurea moştenită de Fibocel sub forma unui dreptunghi cu N linii şi M coloane având doar valori de 0 şi 1, unde 0 înseamnă suprafaţă fără copac iar 1 înseamnă suprafaţă cu copac, spuneţi câte pădurici se regăsesc în interiorul pădurii moştenite.
Date de intrare
Fişierul de intrare mostenire2.in conţine pe prima linie două numere naturale N şi M separate prin exact un spaţiu reprezentând dimensiunea pădurii. Pe fiecare dintre următoarele N linii se găsesc exact M caractere fără spaţiu între ele, având doar valori de 0 şi de 1.
Date de ieşire
Fişierul de ieşire mostenire2.out va conţine exact un număr reprezentând răspunsul cerut de Fibocel.
Restricţii
- 1 ≤ N ≤ 100
- 1 ≤ M ≤ 1000
- Păduricile se pot intersecta între ele.
- Pentru 15% dintre teste N,M ≤ 30.
- Pentru alte 35% dintre teste, M ≤ 100.
Exemplu
mostenire2.in | mostenire2.out |
---|---|
5 4 1111 1010 1111 1010 1110 | 3 |