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:
Teksta faila galerija.dat 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.
Teksta faila galerija.rez vienīgajā rindā jāizvada lielākais iespējamais gleznu skaits,ko iespējams piekārt pie galerijas sienām.
| galerija.dat | galerija.rez |
3 3 XXX X.X XXX |
0 |
| galerija.dat | galerija.rez |
5 5 XXXXX X...X X.XXX X.X.X XXXXX |
4 |
| galerija.dat | galerija.rez |
7 10 XXXXXXXXXX X.X.X....X XXX.X.XX.X XX....XX.X X.XX..X..X X..XX...XX XXXXXXXXXX |
14 |