Dexter

Dexter is very busy. Right now he's not doing experiments and not even creating novel things. He's trying to search for patterns in the drawings of his dippy sister Dee Dee. He is already used to her appearing in his lab, but recently, she has scattered there unusual drawings on grid paper. The drawings are made on rectangular sheets, and they seem like their columns have circles on one another. Dexter made up his mind to cut the cells filled with circles out of the sheets. He wants to cut on each gridline that separates a cell filled with a circle from an empty cell; however, he doesn't want cut between two cells filled with circles. He wants to minimize his efforts, so that he can do this job with the smallest possible number of cuts.

Input Specification

The input contains several test cases. The first line of each test case consists of two positive integers: the height (N) and width (M) of the grid paper (1 ≤ N, M ≤ 100). This is followed by N lines, each containing M characters. An empty cell is denoted by the '.' (dot) character, a filled cell is denoted by the 'O' (capital O) character. To help your job, Dexter has made the following statement: Dee Dee always leaves the top row of the sheet empty, fills the bottom row with circles, and draws a circle into any other cell only if the cells below it are already filled with circles. This way, the filled cells form a single continuous area – this area is to be cut.

Output Specification

For each test case, the program should print the minimum number of cuts required to cut the area filled with circles out of the sheet.

Sample Input

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

download as text file

Output for Sample Input

1. 11
2. 1
3. 11

download as text file