D - Hra16

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Hra16 je hrou jedného hráča, ktorý ju hrá na sa šachovnici s rozmermi 4x4. Každé políčko šachovnice je zafarbené buď čiernou alebo bielou farbou. V jednom ťahu si hráč zvolí ľubovoľné políčko šachovnice, čím toto políčko spolu so všetkými susednými políčkami zmení svoju farbu. Políčka sú susedné, ak sa dotýkajú čo i len v jednom bode. Hra sa končí v okamihu, keď sa dosiahne stav, v ktorom sú na šachovnici, iba biele políčka. Nasledujúci aplet je jednoduchou implementáciou tejto hry.

Úloha

Daná je počiatočná konfigurácia hry. Zistite najmenší možný počet ťahov, ktorý potrebujeme na ukončenie Hry16 z tejto počiatočnej konfigurácie.

Vstup

Prvý riadok vstupu obsahuje počet testovacích sád Q, (1≤Q≤100). Ďalej bude nasledovať Q testovacích sád - popisov počiatočných konfigurácií Hry16. Jeden popis konfigurácie pozostáva zo 4 riadkov, z ktorých každý obsahuje presne 4 znaky '0' alebo '1'. Znak '0' reprezentuje biele políčko a znak '1' čierne políčko počiatočnej konfigurácie. Jednotlivé testovacie sady sú oddelené prázdnym riadkom.

Výstup

Pre každú počiatočnú konfiguráciu vypíšte minimálny počet ťahov, ktorými vieme túto konfiguráciu vyriešiť. Váš program má dokopy vypísať Q čísel, každé v samostatnom riadku.

Poznámka

Každá konfigurácia Hry16 sa dá vyhrať do víťazného konca.

Príklad

Vstup

Výstup

0
1
10

03 Finále 1