Úloha: Polymino

Jiří se ve svých architektonických návrzích občas inspiruje geometrickými objekty známými pod jménem polymina. Jedno polymino je tvar, který vznikne, když se k sobě přiloží hranami několik jednotkových čtverců tak, aby se každé dva sousední čtverce dotýkaly po celé délce hrany.


Obr 1. Některá malá polymina.

Nedávno Jiří získal zakázku na výzdobu radnice ve svém rodném městě. Představuje si, že jednu stěnu obloží několika polyminy. Tvar stěny si rozdělil pravoúhlou sítí na jednotkové čtverce a připravil si několik polymin, která považuje za výtvarně zajímavá. Polymina chce umístit na stěnu tak, aby čtverce z nichž jsou polymina vytvořena, splývaly se čtverci sítě na stěně. Jak ukazuje níže uvedený příklad, možností, jak daná polymina na stěnu umístit, může být více. Jiří by proto ocenil program, který by pro daný tvar stěny a danou množinu polymin vypsal všechny možné způsoby pokrytí stěny. Tato pokrytí budeme nazývat konfigurace.


Obr 2. Přiklad stěny, množiny čtyř polymin a všech tří možných konfigurací.

Spolu s Jiřím budeme předpokládat následující omezení.
    .
  1. Každé polymino lze otočit o 90°, 180°, 270°, nesmí se ale překlápět, t.j. vytvářet jiný, zrcadlový obraz téhož polymina.
  2. Všechna použitá polymina mají různý tvar, t.j. žádná dvě ani po libovolném otočení nesplývají. Některá polymina (která samo nemají osovou souměrnost) však mohou být zrcadlovými obrazy jiných polymin.
  3. Pokud po nějakém otočení splývá polymino samo se sebou, nepovažuje se toto otočení za novou možnost konfigurace. Například polymino o rozměrech 2x1, splývá po otočení o 180° samo se sebou, a proto u něj budeme uvažovat jen o možném otočení o 90°. Polymina velikosti 1x1, 2x2, 3x3 atd. nemá smysl otáčet vůbec.
  4. Polymina nemusí pokrývat stěnu úplně. Pokud některé jednotkové čtverce stěny zůstanou nepokryté, Jiří počítá s tím, že je případně vhodně vyplní později, ne nutně polyminy.
  5. Všechna polymina v daném souboru je nutno použít. Pokud by celkový počet jednotkových čtverců ve všech zadaných polyminech převyšoval počet jednotkových čtverců na stěně, úloha by ovšem neměla řešení.
  6. Velikost stěny je nejvýše 100x100 jednotkových čtverců, velikost každého polymina je nejvýše 10x10 čtverců.
  7. Všechny tvary stěn v naší úloze budou postrádat rotační i osovou symetri. Je to proto, abychom se vyhnuli nejednoznačnostem a otázkám typu, zda jsou pokrytí na obr. x stejná či ne.

Vstup:

Vstupní soubor je textový. První řádek obsahuje obsahuje dvě čísla W H oddělená mezerou, je to šířka a výška stěny. Když má stěna nepravidelný tvar, je to šířka a výška obdélníkové obálky (bounding box/rectangle) stěny. Na dalších H řádcích je matice obsahující jedničky a nuly. Matice představuje čtvercovou síť stěny, jednička představuje stěnu, nula prázdný prostor. Každá řádek matice má W znaků bez mezer nebo oddělovačů. Další řádek obsahuje číslo K udávající počet polymin. Za ním následují jednotlivá polymina definovaná stejným způsobem jako stěna (stěna je z formálního pohledu jedno veliké polymino). Obdélníková obálka těsně přiléhá ke tvaru, který obaluje, proto první a poslední řádek matice, stejně tak i první a poslední sloupec musí obsahovat alespoň jednu jedničku.

Výstup:

Výstup obsahuje všechny možné konfigurace daných polymin na dané stěně vypsané v libovolném pořadí. Konfigurace jsou odděleny prázdným řádkem, za poslední konfigurací je uveden řádek se slovem END a tím výstupní soubor končí. Mezi poslední konfigurací a slovem END je rovněž prázdný řádek (pro programovací pohodlí), pokud je množina konfigurací prázdná, obsahuje výstupní soubor jediný řádek se slovem END (a žádný prázdný řádek). Každá konfigurace je zapsána jako matice reprezentující obdélníkovou obálku stěny. Prvek matice je roven 0, pokud odpovídající čtverec buď leží mimo stěnu nebo není pokryt žádným polyminem. Pokud je odpovídající čtverec pokryt polyminem, je v prvku matice uvedeno pořadové číslo tohoto polymina. Pořadí polymin je dáno jejich pořadím ve vstupním souboru a začíná 1. Rozměry matice se neuvádějí, musí být stejné jako rozměry obdélníkové obálky stěny ve vstupním souboru. Matice neobsahuje mezery ani jiné oddělovače, předpokládáme, že počet polymin je maximálně 9.

Paměť a čas

Velikost použitelné paměti je 1GB, časový limit běhu programu pro každou instanci dat je 10 sec.

Příklad:

Opakujeme situaci z Obr. 2.

Vstup:

5 4
00011
01111
11111
11111
4
2 2
11
11
2 3
01
11
01
1 3
1
1
1
2 3
01
01
11

Výstup:

00023
00223
11423
11444

00004
02224
11244
11333

00011
02411
22444
02333

END

Testovací data

Přiložený soubor obsahuje 10 řešených příkladů, které se jen nemnoho liší od skutečných ostrých příkladů v systému, doporučujeme každému serióznímu zájemci, aby svůj program spustil na poskytnutých vstupních souborech a porovnal své výsledky s poskytnutými výstupními soubory.

Download -- Cvičná data