pento
Un pentomino este un aranjament de 5 patrate unite de-a lungul laturilor lor. Fiecarei piese i se asociaza un cod. Exista 12 piese distincte, ilustrate in figura de mai jos, sub fiecare piesa fiind scris codul asociat:
Pentominourile pot fi combinate (alipite) pentru a realiza diferite forme. Pentru aceasta ele pot fi rotite (cu 90, 180, 270 de grade) sau oglindite. De exemplu, in figura de mai jos cele 12 pentominouri sunt folosite pentru a forma un desen asemanator literei H.
Cerinta
Fiind data o astfel de forma,
se cere sa se gaseasca un mod de obtinere a acestei forme cu ajutorul celor
12 pentominouri. Forma este data printr-o matrice binara cu m
linii si n coloane, elementele
de 1 reprezentand casutele ce
trebuie "acoperite" cu piesele de pentomino, elementele de 0
reprezentand casute libere ce nu vor fi acoperite.
Se stie ca fiecare
pentomino se poate utiliza o singura data. De asemenea se vor utiliza toate
piesele. Piesele nu se pot suprapune. O
solutie a problemei va inlocui in harta initiala valorile binare cu codurile
pieselor ce acopera fiecare celula in parte.
Date de intrare
Pe prima linie a fisierului de intrare pento.in numerele m si n, separate printr-un singur spatiu, reprezentand dimensiunea hartii. Urmatoarele m linii contin cate n cifre binare, reprezentand harta ce trebuie acoperita de pentominouri.
Date de iesire
Fisierul pento.out va contine m linii, fiecare linie continand n numere naturale cuprinse intre 0 si 12 reprezentand modul de acoperire a hartii date.
Restrictii
Exemplu
| pento.in |
pento.out |
Observatii |
| 12
6 110011 110011 110011 111111 111111 111111 111111 111111 110011 111011 111011 111001 |
8 8 0 0 12 9 |
Solutia corespunde formei literei H din imaginea din enunt. |
Timp maxim de executie/test: 0.4 secunde
prof. Carmen
Popescu
Colegiul National
"Gheorghe Lazar" Sibiu
Contact: popescu.carmen@yahoo.com