URI Online Judge | 1907

Colouring Game Scenarios

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

Professor Fernando Bevilacqua is very worried about his newest game's scenarios. The scenarios contours have already been drawn by an artist, and now Professor Bevilacqua has just to colour them. At the present moment, each scenario is an image in which each pixel is black or white. Thus, when Professor Bevilacqua, in his image colouring software, clicks on a white pixel to be coloured with a colour α, all the white region in which the chosen pixel is receives the colour α. We say that a white pixel A is in the same white region of a white pixel B if there is a path between A and B passing only by white pixels and considering the adjacencies only in horizontal and vertical directions. For instance, 6 clicks are needed to colour the figure to the left.


The first input line consists of two positive integers N and M (N, M ≤ 1,024), which represent the image resolution. Each one of the N lines following contains M characters, which can be . (dot) or o (small letter ‘o’), representing respectively a white pixel of a black pixel.


Print a line containing a single integer that represents the number of clicks needed to colour the whole figure described in the input.

Input Samples Output Samples

6 9


1 8


1 1