== include(page="template/taskheader" task_id="bmap") ==
Poveste si cerinta...
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.
h2. Date de intrare
Fisierul de intrare $bmap.in$ ...
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).
h2. Date de iesire
In fisierul de iesire $bmap.out$ ...
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.
h2. 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).
h2. Exemplu
table(example). |_. bmap.in |_. bmap.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
|10 20
00001111111000011110
11110111101111010111
01110000111111001111
11111110000000001111
10000111111111010000
10111011111111011111
10101011111111010001
10111010001001010001
10000010111111010001
11111110001111010001
|5 65
2 16
2|
h3. 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$.
!problema/bmap?bmap.jpg!
== include(page="template/taskfooter" task_id="bmap") ==
