Ú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.
Obr 2. Přiklad stěny, množiny čtyř polymin a všech tří možných konfigurací.
- .
- 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.
- 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.
- 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.
- 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.
- 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í.
- Velikost stěny je nejvýše 100x100 jednotkových čtverců, velikost každého polymina je nejvýše 10x10 čtverců.
- 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