Školsko natjecanje iz informatike / Srednja škola / Prva podskupina (1. i 2. razred) - 2. zadatak (2021)

Beth igra šah u glavi, ali ne uvijek na standardnoj kvadratnoj ploči, nego na pravokutnoj ploči dimenzija R × S i to samo s jednom figurom: skakačem.

Neka polja na ploči su slobodna, a na nekima se nalaze prepreke i na njih skakač ne može skočiti.

Beth stavlja skakača na neko polje ploče i pita se koliko polja (brojeći i početno) skakač može obići krenuvši s tog polja, pri čemu je dopušteno da na neko polje skoči više puta (no i tada ga brojimo samo jednom).

Štoviše, ako može proizvoljno izabrati početno polje skakača, Beth zanima koliko je najviše polja moguće obići u jednom takvom nizu skokova (kojih može biti nula ili proizvoljno mnogo).

Napišite program koji Beth odgovara na to pitanje!

Napomena.

Skakač se kreće kao i u šahu, u obliku slova L. Preciznije, on uvijek skoči za dva polja horizontalno (u bilo kojem smjeru) i jedno polje vertikalno (u bilo kojem smjeru), ili obrnuto, za dva polja vertikalno (u bilo kojem smjeru) i jedno polje horizontalno (u bilo kojem smjeru).

Donja slika dijela ploče prikazuje polja na koja skakač može skočiti u jednom potezu, pod uvjetom da su slobodna i unutar ploče.

ULAZNI PODACI

U prvom retku nalaze se prirodni brojevi R i S (2 ≤ R, S ≤ 10), dimenzije ploče.

U idućih R redaka nalazi se po S brojeva iz skupa {0, 1} odvojenih razmakom.

Broj 1predstavlja slobodno polje, a 0 polje na kojemu se nalazi prepreka. Barem jedno polje na ploči bit će slobodno.

IZLAZNI PODACI

U prvi redak ispišite traženi najveći broj polja.

Primjeri test podataka

Ulaz

2 3
1 1 1
1 1 1

Izlaz

2

Objašnjenje

Objašnjenje prvog primjera: s polja u nekom kutu ploče skakač može skočiti na polje u suprotnom kutu i tako posjetiti ukupno dva polja. S ostalih polja skakač ne može nikamo skočiti.

Ulaz

3 3
1 1 1
1 0 0
1 1 1

Izlaz

7

Objašnjenje

Objašnjenje drugog primjera: moguće je obići sva slobodna polja.