Obława
Limit pamięci: 64 MB
Fifolandia ponownie jest w stanie wojny z Wielką Barańską Gogolską Dżamahirijją Ludową.
Ostała się już tylko ostatnia jednostka nieprzyjaciela, która ukryła się gdzieś w lesie.
Kapral Fifuś jest odpowiedzialny za zorganizowanie obławy na oddział nieprzyjaciela.
W związku z tym Fifuś szybko znalazł mapę lasu o rozmiarze , na której dla każdego
jednostkowego kwadratu oznaczone jest, czy znajdują się na nim bagna, czy też nie.
Na mapie pola, na których jest bagno, są oznaczone jako , natomiast pozostałe pole,
na których nie ma bagien, są oznaczone jako .
Oczywiście oddziały Fifusia nie mogą stacjonować na obszarze, na którym znajduje się bagno.
Ponadto w wojskowym prawie Fifolandii jest dokładnie określone, jak powinna wyglądać obława,
a Fifuś musi przestrzegać tych zasad.
Zgodnie z wojskowym prawem Fifolandzkim otaczając
przeciwnika, należy tak rozmieścić wojska, aby tworzyły obwód kwadratu o boku co najmniej .
Podobno takie rozmieszczenie gwarantuje, że wojskom przeciwnika nie uda się uciec.
Na nieszczęście Fifuś nie ma najmniejszego pojęcia, gdzie mogą znajdować się wojska przeciwnika.
Dlatego zanim Fifuś zdecyduje, w którym miejscu rozpocząć obławę, zastanawia się, na ile sposobów można
to zrobić.
Zakładamy, że wojska Fifolandii nie będą miały problemów z dotarciem w dowolne miejsce,
które nie jest bagnem - mogą do tego użyć np. helikopterów.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą długość boku mapy.
Następnie na wejściu pojawi się wierszy. W -tym wystąpi ciąg cyfr
- zera lub jedynki. Jeżeli ,
oznacza to, że na danym polu jest bagno, natomiast oznacza, że na danym polu nie ma bagna.
Możesz założyć, że w testach wartych około zachodzi dodatkowy warunek .
Wyjście
Pierwszy wiersz standardowego wyjścia powinien zawierać jedną liczbę całkowitą,
równą liczbie sposobów, na które Fifuś może rozmieścić wojska.
Przykład
Dla danych wejściowych:
6
111110
101010
011111
011101
101011
011111
poprawną odpowiedzią jest:
5
Wyjaśnienie do przykładu:
Fifuś może rozmieścić wojsko na obwodzie kwadratów, których współrzędne lewego górnego rogu to:
- , bok długości ,
- , bok długości ,
- , bok długości .
Autor zadania: Łukasz Jocz.