== 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. 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ă. $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$.

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ă. $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|

Să se determine numărul total de zone dreptunghiulare din matrice, ordinul maxim al unei zone şi numărul de zone care au acest ordin maxim.

h2. Date de intrare

Fişierul de intrare $dreptunghiuri2.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 $dreptunghiuri2.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

h3. Explicaţii

Sunt în total $4$ zone dreptunghiulare, ordinul maxim al uneia dintre ele este $3$ (cea formată dintr-un singur $1$) şi există o singură astfel de zonă.

Sunt în total $4$ zone dreptunghiulare ordinul maxim al uneia dintre ele este $3$
(cea formată dintr-un singur $1$) şi este o singură astfel de zonă.

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

4748