Úloha: Netradiční šachovnice
Jiří se nedávno stal společníkem ve firmě, která se zabývá vývojem a prodejem netradičních deskových her. Jednou z aktuálních úloh je prozkoumat varianty šachové hry na šachovnici o jiném tvaru než obyčejných 8 x 8 polí. Varianty na obdélníkových šachovnicích různých rozměrů jsou poměrně známé. Naproti tomu varianty na šachovnicích nepravidelného tvaru jsou spíše ojedinělé a Jiří se rozhodl vyzkoušet tuto cestu. Mezi jiným, jako hlavolam pro zákazníky, řeší klasickou úlohu, jaký je maximální počet šachových dam, které je možno na šachovnici -- tentokrát netradiční -- postavit, aniž by se navzájem ohrožovaly. Netradiční šachovnice se skládá z černých a bílých čtvercových polí, které se dotýkají svými hranami stejně jako na klasické šachovnici, rozdíl je ale v tom, že na netradiční šachovnici může libovolný počet polí na libovoných místech chybět a stejně tak velikost šachovnice může být libovolná. Dvě dámy na šachovnici se ohrožují právě tehdy pokud stojí na stejném sloupci nebo na stejném řádku nebo na stejné diagonále a přitom mezi nimi v příslušném sloupci/řádku/diagonále není ani jedno chybějící pole.
Obr 1. Příklad: Na uvedené šachovnici se navzájem ohrožují právě následující dvojice dam:
(1, 2), (1, 3), (1, 4), (3, 4). Chybějící pole uvnitř šachovnice jsou znázorněna tmavou barvou, celkem je na této šachovnici 16 polí.
Vstup:
První řádek vstupu obsahuje obsahuje dvě celá čísla H W oddělená mezerou, je to výška (počet řádků) a šířka (počet sloupců) šachovnice. Když má šachovnice nepravidelný tvar, je to šířka a výška obdélníkové obálky (bounding box/rectangle) šachovnice. Na dalších H řádcích je obdélníková matice obsahující jedničky a nuly. Matice představuje čtvercovou síť šachovnice, jednička představuje regulérní pole, nula představuje chybějící pole. Každý řádek matice má W cifer 0/1 bez mezer nebo oddělovačů. Poznámka: Obdélníková obálka těsně přiléhá ke tvaru, který obaluje, proto první a poslední řádek matice stejně jako její první a poslední sloupec musí obsahovat alespoň jednu jedničku. Obálka šachovnice má rozměr nejvýše 32 x 32 polí, počet polí na šachovnici tak nepřevyšuje 1024.Výstup:
Výstup obsahuje řádek s jediným celým číslem, jímž je maximální počet všech navzájem se neohrožujících dam, které lze postavit na danou šachovnici.Příklad 1:
Vstup:3 6 001011 111111 100101Výstup
5Uvedený výsledek je způsoben např. konfigurací dam:
+---+ +---+---+
|.Q.| |.Q.|...|
+---+---+---+---+---+---+
|.Q.|...|...|...|...|...|
+---+---+---+---+---+---+
|...| |.Q.| |.Q.|
+---+ +---+ +---+
Příklad 2:
Vstup:1 10 1111111111Výstup
1Uvedený výsledek je způsoben např. konfigurací dam:
+---+---+---+---+---+---+---+---+---+---+ |.Q.|...|...|...|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+---+---+
Příklad 3:
Vstup:3 3 111 001 111Výstup
3Uvedený výsledek je způsoben konfigurací dam:
+---+---+---+
|.Q.|...|...|
+---+---+---+
|.Q.|
+---+---+---+
|.Q.|...|...|
+---+---+---+
Příklad 4:
Vstup:5 5 10101 11111 01010 11111 10101Výstup
8Uvedený výsledek je způsoben konfigurací dam:
+---+ +---+ +---+
|.Q.| |.Q.| |.Q.|
+---+---+---+---+---+
|...|...|...|...|...|
+---+---+---+---+---+
|.Q.| |.Q.|
+---+---+---+---+---+
|...|...|...|...|...|
+---+---+---+---+---+
|.Q.| |.Q.| |.Q.|
+---+ +---+ +---+
Příklad 5:
Vstup:8 8 11111111 10111101 10100101 10111101 10111101 10100101 10111101 11111111Výstup
9Uvedený výsledek je způsoben např. konfigurací dam:
+---+---+---+---+---+---+---+---+ |...|.Q.|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+ |...| |...|.Q.|...|...| |.Q.| +---+ +---+---+---+---+ +---+ |.Q.| |...| |.Q.| |...| +---+ +---+---+---+---+ +---+ |...| |.Q.|...|...|...| |...| +---+ +---+---+---+---+ +---+ |...| |...|...|.Q.|...| |...| +---+ +---+---+---+---+ +---+ |...| |...| |...| |...| +---+ +---+---+---+---+ +---+ |...| |...|.Q.|...|...| |...| +---+---+---+---+---+---+---+---+ |...|.Q.|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+