dreptunghiuri2

Dreptunghiuri2

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

Poveste şi cerinţă...

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.

h2. Date de intrare

 
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. Date de intrarest

Fişierul de intrare $dreptunghiuri2.in$ ...