Nosaukums
Gleznu galerija (galerija)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
89%

Definīcija

Galerijas karti iespējams attēlot kā M rindu un N kolonnu rūtiņu laukumu. Dažas no rūtiņām atbilst sienām, bet citas tukšiem laukumiem.

Istabas sastāv no blakus esošām (tādām, kurām ir kopīga mala) tukšām rūtiņām. Uz istabu sienām mēs vēlamies izvietot pēc iespējas vairāk gleznu. Katra glezna aizņem tieši divus rūtiņu malu garumus (to augstums nav būtisks). Citiem vārdiem, gleznu var piekārt pie sienas tad, ja ir divas blakusesošas sienas un to priekšā ir divas tukšas rūtiņas (protams, tajā pašā sienu pusē).

Uzrakstiet programmu, kas atrod lielāko iespējamo gleznu skaitu, kuras var piekārt pie sienām!

Zīmējumā redzams viens no iespējamiem atrisinājumiem:


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu M(galerijas rindu skaits) un N(galerijas kolonnu skaits) vērtības, kas atdalītas ar tukšumsimbolu. Zināms, ka 1 ≤M,N≤1000.

Katrā no nākošajām M faila rindām dots pa N simboliem katrā un katra apraksta vienu galerijas rindu pēc kārtas. Katrs simbols 'X' rindā apzīmē sienu, bet '.' - tukšu rūtiņu.

Pirmā un pēdējā galerijas rinda, tāpat kā pirmā un pēdējā galerijas kolonna ir sienas.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada lielākais iespējamais gleznu skaits,ko iespējams piekārt pie galerijas sienām.


Piezīmes

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā


Paraugdati

Stdin
5 5
XXXXX
X...X
X.XXX
X.X.X
XXXXX
Stdout
4

Stdin
7 10
XXXXXXXXXX
X.X.X....X
XXX.X.XX.X
XX....XX.X
X.XX..X..X
X..XX...XX
XXXXXXXXXX
Stdout
14

Stdin
3 3
XXX
X.X
XXX
Stdout
0

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.