Problem description
Istnieje taki edytor tekstu (a może system operacyjny bez edytora tekstu) Emacs. Jako zaawansowane narzędzie do edycji tekstu zawiera w sobie kilka umilaczy. Między innymi grę 5x5. Zasady są proste: mamy dany kwadrat 5 × 5, w którym niektóre pola są zapalone, a niektóre zgaszone. W jednym ruchu możemy wybrać pole i zmienić jego stan (z zapalonego na zgaszony i na odwrót), przy czym zmienia się też stan pola nad nim, pod nim, na lewo od niego oraz na prawo od niego (jeśli takie istnieją). Celem w grze jest zgaszenie wszystkich pól. Rozważmy tę grę nieco ogólniej. Będziemy analizowali grę na tych samych zasadach, lecz plansza może być kwadratem o dowolnym boku długości N, a nie tylko 5.
Napisz program, który: wczyta długość boku kwadratu oraz konfigurację początkową planszy, obliczy minimalną liczbę ruchów niezbędną do zwycięstwa lub stwierdzi, że zwycięstwo jest nieosiągalne, wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca długość boku
kwadratowej planszy. W kolejnych N wierszach znajduje się opis
kwadratowej planszy. Każdy wiersz zawiera dokładnie N cyfr 0 lub
1, pooddzielanych pojedynczymi odstępami, gdzie
0 oznacza, że dane pole jest zgaszone, natomiast
1 – zapalone.
Wyjście
W pierwszym i jedynym wierszu wyjścia należy wypisać dokładnie jedną
liczbę całkowitą – minimalną liczbę ruchów niezbędną do zwycięstwa.
Jeśli zwycięstwo jest niemożliwe – należy wypisać NIE.
Ograniczenia
3 ≤ N ≤ 16.
Przykład
| Wejście | Wyjście | |
|
|