bmap

Bmap

== include(page="template/taskheader" task_id="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 direct sau prin intermediul altor elemente, 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 si 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.

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

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).

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

h2. Restrictii

* $1 ≤ M ≤ 1000$
* $1 ≤ N ≤ 10000$
* 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).

* $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

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.

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!