| Fişierul intrare/ieşire: | bmap.in, bmap.out | Sursă | Happy Coding 2008 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 1.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bmap
Se da o matrice binara (elementele sunt 0 sau 1) avand M linii si N coloane. O componenta neagra este o submultime de elemente cu valoarea 1, cu proprietatea ca se poate ajunge de la orice element din componenta la orice alt element al componntei, direct sau prin intermediul altor elemente din componenta, efectuand deplasari pe directiile orizontala si/sau verticala (asadar, dintr-un element se poate ajunge direct intr-unul din cele maxim 4 elemente vecine din jurul sau). O componenta neagra se numeste compacta daca nu contine nici un element alb in interiorul acesteia (mai exact, daca exista un ciclu format din o parte din elemente componentei, mergand doar pe directiile orizontala si verticala, care sa contina un element alb in interior, atunci componenta NU este compacta). Dimensiunea unei componente negre este egala cu numarul de elemente din care este compusa. Se defineste adancimea unei componente negre ca fiind egala cu 1 + numarul de componente negre in interiorul careia aceasta este inclusa.
Determinati numarul total de componente negre, dimensiunea celei mai mari componente negre, numarul total de componente negre compacte si dimensiunea celei mai mari componente negre compacte. De asemenea, determinati adancimea maxima a unei componente negre.
Date de intrare
Prima linie a fisierului de intrare bmap.in contine doua numere intregi, separate printr-un spatiu: M si N. Urmatoarele M linii contin cate N caractere din multimea {'0','1'}, neseparate prin spatii ('0'=element alb, '1'=element negru).
Date de iesire
Pe prima linie a fisierului de iesire bmap.out veti afisa 2 numere intregi, separate printr-un spatiu: numarul total de componente negre si dimensiunea celei mai mari componente negre. Pe a doua linie veti afisa alte 2 numere intregi, separate printr-un spatiu: numarul de componente negre compacte si dimensiunea celei mai mari componente negre compacte. Pe a treia linie veti afisa adancimea maxima a unei componente negre.
Restrictii
- 1 ≤ M ≤ 10000
- 1 ≤ N ≤ 1000
- Daca nu exista nicio componenta neagra compacta, dimensiunea celei mai mari componente nerge compacte se considera a fi 0.
- Daca nu exista nicio componenta neagra, dimensiunea celei mai mari componente negre se considera a fi 0 (la fel si adancimea maxima).
Exemplu
| bmap.in | bmap.out |
|---|---|
| 10 20 00001111111000011110 11110111101111010111 01110000111111001111 11111110000000001111 10000111111111010000 10111011111111011111 10101011111111010001 10111010001001010001 10000010111111010001 11111110001111010001 | 5 65 2 16 2 |
Explicatie
Matricea binara din exemplu este desenata in figura de mai jos. Se observa ca exista 5 componente negre (numerotate de la 1 la 5), din care componentele 1, 2 si 3 NU sunt compacte. Componenta 4 este compacta, deoarece nu contine nici un patratel alb in interior. Cea mai mare componenta neagra are dimensiunea 65 (componenta 3), iar cea mai mare componenta neagra compacta are dimensiunea 16 (componenta 4). Componenta 2 are adancimea 2 (fiind inclusa in componenta 3), iar celelalte componente au adancimea 1.
