.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » pento

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
pento


Timp maxim de executie/test:
0.4 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

  • 3 <= m,n <= 100

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
8 8 0 0 12 9
2 8 0 0 12 9
2 2 2 12 12 9
2 7 6 6 10 9
7 7 7 6 10 10
7 3 3 6 6 10
3 3 1 1 1 10
3 4 0 0 1 11
4 4 4 0 1 11
5 4 5 0 11 11
5 5 5 0 0 11

Solutia corespunde formei literei H din imaginea din enunt.

 

prof. Carmen Popescu
Colegiul National "Gheorghe Lazar" Sibiu
Contact: popescu.carmen@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor