== include(page="template/taskheader" task_id="dreptunghiuri2") ==

Se consideră o matrice cu elemente 0 sau 1, cu L linii (numerotate de la 1 la L) şi C coloane (numerotate de la 1 la C).
Definim o zonă dreptunghiulară ca fiind o submatrice ce are pe contur numai valori 1 şi cu proprietatea că nu există valori de 1 nesituate pe contur şi în acelaşi timp la distanţa 1 faţă de un punct de pe contur. Două puncte sunt la distanţa 1 dacă şi numai dacă sunt vecine pe una dintre cele 8 direcţii.

Se consideră o matrice cu elemente $0$ sau $1$, cu $L$ linii (numerotate de la $1$ la $L$) şi $C$ coloane (numerotate de la $1$ la $C$).
Definim o zonă dreptunghiulară ca fiind o submatrice ce are pe contur numai valori $1$ şi cu proprietatea că nu există valori de $1$ nesituate pe contur şi în acelaşi timp la distanţa $1$ faţă de un punct de pe contur. Două puncte sunt la distanţa $1$ dacă şi numai dacă sunt vecine pe una dintre cele $8$ direcţii.

Interiorul unei zone dreptunghiulare constă din elementele din submatrice nesituate pe contur.

O zonă dreptunghiulară poate fi inclusă complet în interiorul alteia. Definim ordinul unei zone dreptunghiulare ca fiind valoarea d+1, unde d este numărul de zone în interiorul cărora aceasta este inclusă.
Orice element 1 din matrice se află pe conturul unei singure zone dreptunghiulare.
Fig. 1-4 conţin exemple de zone dreptunghiulare. În fig. 5 este o matrice în care se găsesc trei zone dreptunghiulare, dintre care zonele din interior au ordinul 2 iar cealaltă ordinul 1.

O zonă dreptunghiulară poate fi inclusă complet în interiorul alteia. Definim ordinul unei zone dreptunghiulare ca fiind valoarea $d+1$, unde $d$ este numărul de zone în interiorul cărora aceasta este inclusă.
Orice element $1$ din matrice se află pe conturul unei singure zone dreptunghiulare.
$Fig. 1-4$ conţin exemple de zone dreptunghiulare. În $fig. 5$ este o matrice în care se găsesc trei zone dreptunghiulare, dintre care zonele din interior au ordinul $2$ iar cealaltă ordinul $1$.

table(example). |_. fig. 1 |_. fig. 2 |_. fig. 3|_. fig.4|_. fig. 5|

h2. Date de intrare

Fişierul de intrare dreptunghiuri.in conţine pe prima linie numerele naturale L şi C separate printr-un spaţiu. Pe fiecare din următoarele L linii din fişier se află câte C numere din mulţimea {0,1}, separate prin câte un spaţiu, reprezentând valorile din matrice.

Fişierul de intrare dreptunghiuri.in conţine pe prima linie numerele naturale $L$ şi $C$ separate printr-un spaţiu. Pe fiecare din următoarele $L$ linii din fişier se află câte $C$ numere din mulţimea ${0,1}$, separate prin câte un spaţiu, reprezentând valorile din matrice.

h2. Date de ieşire

Fişierul de ieşire dreptunghiuri.out conţine pe prima linie trei numere naturale D, O şi NR, separate prin câte un spaţiu, unde D este numărul total de zone dreptunghiulare din matrice, O este ordinul maxim al unui astfel de zone, iar NR este numărul de zone de ordin maxim.

Fişierul de ieşire dreptunghiuri.out conţine pe prima linie trei numere naturale $D$, $O$ şi $NR$, separate prin câte un spaţiu, unde D este numărul total de zone dreptunghiulare din matrice, $O$ este ordinul maxim al unui astfel de zone, iar $NR$ este numărul de zone de ordin maxim.

h2. Restricţii
* $3 ≤ L, C ≤ 1 000$
* Datele de intrare sunt corecte. Va exista cel puţin o zonă dreptunghiulară în matrice.

* Pentru determinarea corectă a numărului de zone se acordă 20% din punctajul pe fiecare test.

* Pentru determinarea corectă a numărului de zone se acordă $20%$ din punctajul pe fiecare test.

h2. Exemplu
table(example). |_. dreptunghiuri2.in |_. dreptunghiuri2.out |_. Explicaţii|

| 9  12

| 9 12

0 1 1 1 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 1
0 1 0 1 1 1 1 1 0 0 0 1