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.
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
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.
Output for Sample Input
|University of Debrecen; Faculty of Informatics; v. 03/01/2019|