Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | dreptunghiuri2.in, dreptunghiuri2.out | Sursă | ONI 2010, clasa a 10-a |
| Autor | Marius Nicoli | Adăugată de |  Dragos-Alin Rotaru •mathboy |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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ă.
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.
| 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 |
Date de intrarest
Fişierul de intrare dreptunghiuri2.in ...
Date de ieşire
În fişierul de ieşire dreptunghiuri2.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| dreptunghiuri2.in | dreptunghiuri2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
