== 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$.
table(example). |_. fig. 1 |_. fig. 2 |_. fig. 3|_. fig.4|_. fig. 5|
| 1 1 1 1 1
1 0 0 0 1
1 1 1 1 1
| 1 1 1
| 1
| 1 1 1 1
1 1 1 1
| **1 1 1 1 1 1 1 1 1** 0
**1** 0 0 0 0 0 0 0 **1** 0
**1** 0 **1 1 1** 0 **1** 0 **1** 0
**1** 0 **1** 0 **1** 0 **1** 0 **1** 0
**1** 0 **1 1 1** 0 **1** 0 **1** 0
**1** 0 0 0 0 0 0 0 **1** 0
**1 1 1 1 1 1 1 1 1** 0
|
h2. Cerinţă
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.
Poveste şi cerinţă...
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 $dreptunghiuri2.in$ ...
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.
În fişierul de ieşire $dreptunghiuri2.out$ ...
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.
* Orice element $1$ din matrice se află pe conturul unei singure zone dreptunghiulare.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. dreptunghiuri2.in |_. dreptunghiuri2.out |
| 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
0 1 0 1 0 0 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1
0 1 0 1 0 0 0 1 0 1 0 1
0 1 0 1 1 1 1 1 0 1 0 1
0 1 0 0 0 0 0 0 0 0 0 1
0 1 1 1 1 1 1 1 1 1 1 1
| 4 3 1
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţii
h3. Explicaţie
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ă.
...
== include(page="template/taskfooter" task_id="dreptunghiuri2") ==
