Državno natjecanje iz informatike 2019. / Prva podskupina (1. i 2. razred) - 2. zadatak

Poljodjelac Željko ima zemljište dimenzija R × S metara koju predstavljamo matricom od R × S polja. Za svaki kvadratni metar zemljišta (za svako polje) Željko zna je li zemlja na njemu plodna ili neplodna.

Željko je odlučio na svojoj parceli posaditi novu biljku koja se brzo širi. On će odabrati neku dijagonalu zemljišta (bilo koji dijagonalni niz polja) i potom:

1. Sva neplodna polja na odabranoj dijagonali (ako takvih ima) Željko će pognojiti i tako učiniti plodnima.
2. Posadit će po jednu biljku na svako polje odabrane dijagonale.
3. Svaka izrasla biljka proširit će svoje sjeme na svako susjedno plodno polje, na kojemu će onda također izrasti ista biljka. Susjedstvo definiramo u četiri smjera, tj. polja su susjedna kada dijele zajedničku stranicu.
4. Širenje iz prethodne točke nastavlja se za sve novoizrasle biljke i njima susjedna plodna polja dok god je to moguće.

(Za ilustraciju pogledajte pojašnjenja donjih primjera.)

Pomozite Željku odabrati početnu dijagonalu na kojoj će saditi biljke.

Preciznije, napišite program koji računa najveći mogući broj biljaka koji Željko može imati na svojem zemljištu nakon opisanog postupka.

ULAZNI PODACI

U prvom su retku prirodni brojevi R i S (3 ≤ R, S ≤ 2000), dimenzije zemljišta.

Sljedećih R redaka sadrži po S znakova (bez razmaka) koji opisuju Željkovo zemljište. Znak '1' predstavlja plodno polje, a '0' neplodno polje.

IZLAZNI PODACI

U jedini redak ispišite traženi najveći broj biljaka.

Primjeri test podataka

Ulaz

5 6
010100
100100
000110
100111
010011

Izlaz

15

Ulaz

8 8
00010011
00010001
00010000
11111111
00010000
00010010
10010111
11010010

Izlaz

26