Fişierul intrare/ieşire:bmap.in, bmap.outSursăHappy Coding 2008
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test3.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/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.inbmap.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?