Školsko natjecanje iz informatike / Srednja škola / Druga podskupina (3. i 4. 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.

U svakom slobodnom polju, prema Bethinoj mašti, nalazi se neki broj zelenih bombona.

Beth stavlja skakača na neko polje ploče i pita se koliko bombona skakač može skupiti krenuvši s tog polja, pri čemu je dopušteno da na neko polje skoči više puta (no bombone će pokupiti samo jednom).

Štoviše, ako može proizvoljno izabrati početno polje skakača, Beth zanima koliko je najviše bombona moguće skupiti 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).

Desna 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, 2, . . . , 10} odvojenih razmakom.

Broj 0 predstavlja polje na kojemu se nalazi prepreka, a svaki pozitivan broj odgovara broju bombona na slobodnom polju.

Barem jedno polje na ploči bit će slobodno, tj. neće biti označeno brojem 0.

IZLAZNI PODACI

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

Primjeri test podataka

Ulaz

2 3
1 4 3
5 4 6

Izlaz

8

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.

U jednom takvom slučaju može skupiti 1 + 6 = 7 bombona, a u drugom 3 + 5 = 8 bombona. S ostalih polja (gdje može skupiti po 4 bombona) 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.