F1 - Veže na šachovniciČasový limit: 2s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3.4, Python 3.11Počet bodov: 1 [ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] Istotne poznáte problém umiestnenia 8 dám na šachovnici tak, aby sa neohrozovali. Dnes sme pre vás pripravili nový problém. Daná je šachovnica, na ktorej je umiestnených niekoľko pešiakov. Umiestnite na túto šachovnicu čo najviac veží tak, aby sa žiadne dve veže navzájom neohrozovali. Dve veže sa navzájom ohrozujú práve vtedy, ak sa nachádzajú v tom istom riadku alebo v tom istom stĺpci, pričom v riadku resp. stĺpci medzi nimi sa nenachádza žiadna iná figúrka. Na každé políčko je možné umiestniť maximálne jednu figúrku.VstupPrvý riadok vstupu obsahuje kladné celé číslo Q, určujúce počet testovacích sád. Prvý riadok testovacej sady obsahuje dve kladné celé čísla N, M, určujúce rozmer šachovnice. Každý z nasledujúcich N riadkov obsahuje presne M znakov. Znak '0' reprezentuje prázdne políčko, znak '1' reprezentuje políčko vyplnené pešiakom.VýstupPre každú sadu zo vstupu vypíšte jedno číslo, určujúce maximálny počet veží, ktoré je možné umiestniť na šachovnicu tak, aby sa neohrozovali.F11 ≤ N,M ≤ 10F21 ≤ N,M ≤ 50PríkladVstup:2 2 3 010 000 4 5 00101 10000 00001 01000 Výstup:3 6 Vysvetlenie výstupu:Optimálne riešenie pre prvú šachovnicu umiestní 3 veže nasledujúcim spôsobom:x1x 0x0Jedno z optimálnych riešení pre druhú šachovnicu vyzerá následovne: x01x1 1x000 00x01 x100xZnak 'x' označuje umiestnenú vežu. |