Dexter

Dexter nagyon elfoglalt. Most épp nem kísérletet végez, de még csak nem is valami újszerű dolgot alkot, hanem az ütődött nővére, Dee Dee rajzaiban próbál mintázatokat keresni. Azt már megszokta, hogy a nővére rendszerint megjelenik a laborjában, ám mostanában szokatlan, négyzetrácsos lapokra rajzolt mintákat dobál ott szét. A rajzok téglalap alakú lapokra készülnek, s úgy néznek ki, mintha az oszlopokban Dee Dee köröket halmozna egymásra. Dexter elhatározta, hogy kivágja a körökkel teli cellákat a papírlapokból. Minden olyan rácsvonalon vágni szeretne, amely egy körrel teli cellát egy üres cellától választ el, ugyanakkor a körökkel teli cellák között sosem szeretni nyisszantani. Az erőfeszítéseit minimalizálni szeretné, ezért az a cél, hogy a feladatot minél kevesebb vágással elvégezhesse.

A bemenet specifikációja

Egy bemenet több tesztesetet tartalmaz. Minden teszteset első sorában két pozitív egész szám szerepel: a négyzetrácsos lap magassága (N), valamint szélessége (M), ahol 1 ≤ N, M ≤ 100. Ezt pontosan N darab olyan sor követi, mely M darab karaktert tartalmaz. Egy üres cellát a '.' (pont) karakter, míg egy kitöltött cellát egy (nagy) 'O' karakter jelöl. A munkádat segítendő Dexter már tett egy megállapítást: Dee Dee a lap legfelső sorát mindig üresen hagyja, a legalsó sorát mindig kitölti, míg a további cellákba akkor rajzol csak kört, ha az azok alatti cellákban is szerepelnek körök (így a kitöltött négyzetek egyetlen egybefüggő területet alkotnak – ezt kell kivágni).

A kimenet specifikációja

A program minden tesztesetre írja ki rajz kivágásához szükséges nyisszantások minimális számát.

Példa bemenet

1. 5 10
2. ..........
3. O....OO...
4. OO..OOO...
5. OOOOOOOOO.
6. OOOOOOOOOO
7. 2 10
8. ..........
9. OOOOOOOOOO
10. 5 7
11. .......
12. O.....O
13. OO...OO
14. OO.O.OO
15. OOOOOOO

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 11
2. 1
3. 11

letöltés szöveges állományként