Jest sobie szachownica n x n, w każdym jej małym kwadraciku jest lampka. Naszym zadaniem jest zgaszenie wszystkich lampek. Dostępną operacją jest zmiana stanu lampek (zapalona->zgaszona lub zgaszona->zapalona), zawartych w pewnym krzyżyku, czyli w 5 polach: (x,y), (x,y+1), (x+1,y), (x,y-1) i (x-1,y). Pole (x,y) musi zawsze mieścić się w szachownicy, a jeżeli któreś z pozostałych pól się nie mieści, to je pomijamy (czyli krzyżyk może mieć tylko 4, a nawet tylko 3 elementy, jeżeli jego środek jest położony przy ścianie szachownicy bądź w rogu).
Napisz program, który:
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (2 <= n <= 10), oznaczająca rozmiar szachownicy. Kolejnych n wierszy zawiera po n cyfr 0/1, bez jakichkolwiek odstępów. 0 oznacza lampkę zgaszoną, 1 - zapaloną.
W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą. Jeżeli nie da się zgasić wszystkich lampek, poprawną odpowiedzią jest -1. W przeciwnym wypadku powinna zostać wypisana minimalna liczba ruchów, konieczna do zgaszenia wszystkich lampek.
Dla danych wejściowych:
3 101 001 100
poprawnym wynikiem jest:
3
Przykładowa sekwencja ruchów (x i y podane z zakresu 0..n-1):
po ruchu x=2,y=0:
101 101 010
po ruchu x=0,y=1:
010 111 010
po ruchu x=1,y=1:
000 000 000
[Zgłoś rozwiązanie] [Moje zgłoszenia]