Netradiční šachovnice
Zadání
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×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 libovolný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.
Vstup
První řádek vstupu 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×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říklady
Příklad 1
3 6
001011
111111
1001015Uvedený výsledek je způsoben např. konfigurací dam:
+---+ +---+---+
|.Q.| |.Q.|...|
+---+---+---+---+---+---+
|.Q.|...|...|...|...|...|
+---+---+---+---+---+---+
|...| |.Q.| |.Q.|
+---+ +---+ +---+
Příklad 2
1 10
11111111111Uvedený výsledek je způsoben např. konfigurací dam:
+---+---+---+---+---+---+---+---+---+---+ |.Q.|...|...|...|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+---+---+
Příklad 3
3 3
111
001
1113Uvedený výsledek je způsoben konfigurací dam:
+---+---+---+
|.Q.|...|...|
+---+---+---+
|.Q.|
+---+---+---+
|.Q.|...|...|
+---+---+---+
Příklad 4
5 5
10101
11111
01010
11111
101018Uvedený výsledek je způsoben konfigurací dam:
+---+ +---+ +---+
|.Q.| |.Q.| |.Q.|
+---+---+---+---+---+
|...|...|...|...|...|
+---+---+---+---+---+
|.Q.| |.Q.|
+---+---+---+---+---+
|...|...|...|...|...|
+---+---+---+---+---+
|.Q.| |.Q.| |.Q.|
+---+ +---+ +---+
Příklad 5
8 8
11111111
10111101
10100101
10111101
10111101
10100101
10111101
111111119Uvedený výsledek je způsoben např. konfigurací dam:
+---+---+---+---+---+---+---+---+ |...|.Q.|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+ |...| |...|.Q.|...|...| |.Q.| +---+ +---+---+---+---+ +---+ |.Q.| |...| |.Q.| |...| +---+ +---+---+---+---+ +---+ |...| |.Q.|...|...|...| |...| +---+ +---+---+---+---+ +---+ |...| |...|...|.Q.|...| |...| +---+ +---+---+---+---+ +---+ |...| |...| |...| |...| +---+ +---+---+---+---+ +---+ |...| |...|.Q.|...|...| |...| +---+---+---+---+---+---+---+---+ |...|.Q.|...|...|...|...|...|...| +---+---+---+---+---+---+---+---+