Državno natjecanje iz informatike 2016. / Druga podskupina (3. i 4. razred) – Prvi dan natjecanja - 2. zadatak

Stado ovaca mirno pase na pašnjaku te ih je potrebno ograditi kako ih ne bi dohvatile divlje zvijeri.

Pritom možemo izgraditi najviše dva ograđena prostora, a cilj nam je da ukupna potrebna duljina ograde bude što manja.

Za ovu priliku, pašnjak je pravokutnog oblika te se sastoji kvadratnih travnatih polja duljine stranice jedan metar organiziranih u n redova i m stupaca.

Svaka ovca nalazi se u nekome od polja, a svako polje sadrži najviše jednu ovcu.

Tor je skup od jednog ili više polja za kojeg vrijedi:

• Sva polja koja su dio tora su međusobno povezana – moguće je od svakog polja doći do svakog drugog polja tako da se u svakom koraku pomaknemo na susjedno polje gore, dolje, lijevo ili desno te da cijelim putem ostanemo unutar tora.

Kako bi se ogradio određeni tor T potrebno je osigurati onoliko dužinskih metara ograde koliko ima susjednih (gore, dolje, lijevo ili desno) parova polja od kojih je jedno polje unutar T, a drugo nije.

Potrebno je konstruirati najviše dva tora.

Naravno, svaka ovca odnosno polje na kojem pase mora biti dio nekog tora, a torovi ne smiju imati zajedničkih niti susjednih polja.

Pronađite najmanju potrebnu ukupnu duljinu ograda.

Ulazni podaci

U prvom redu nalaze se prirodni brojevi n i m (n, m ≤ 1000) – dimenzije pašnjaka.

U svakom od sljedećih n redova nalazi se niz od točno m znakova koji predstavlja jedan redak pašnjaka.

Ovca je označena velikim slovom “O” a prazno polje znakom “.” (točka).

Možete pretpostaviti da će se na pašnjaku nalaziti barem jedna ovca.

Izlazni podaci

Ispišite jedan prirodni broj – najmanju potrebnu ukupnu duljinu ograda.

Primjer zadatka

Ulaz

4 4
....
.OO.
.OO.
....

Izlaz

8

Objašnjenje

Ulaz

3 8
OO...O.O
O.......
.....O.O

Izlaz

20

Objašnjenje