Problem: Cartography

Want to try solving this problem? You can submit your code online if you log in or register.

Cartography

Input File: cartin.txt
Output File: cartout.txt
Time Limit: 0.333 second

You have been contracted by a company which is mapping Pacific islands. They have been taking photographs of the islands from aircraft to produce their maps. The photographs have been converted to grids showing where land is present and where there is water.

You have been called in to help the map makers count the number of islands in their photos. This task is complicated by the fact that some of the islands have lakes and lagoons, which show up as water in the photographs. For example, consider the photograph

..X..XX.
.XX..X.X
.X...X.X
.XX..XXX
....X..X
...XXX..
...X.X..
XX.XXX..

in which an X denotes land and a . denotes water. This photograph contains four islands - they have been designated A, B, C, and D in the diagram below:

..A..BB.
.AA..B.B
.A...B.B
.AA..BBB
....C..B
...CCC..
...C.C..
DD.CCC..

Note that two land squares in the grid are considered adjacent if they share an edge horizontally or vertically (not diagonally). Two land squares are part of the same island if they can be reached from one another via a sequence of adjacent land squares.

In the event an island contains a lake which contains an island, the two islands are counted as separate islands. For example, the map

.XXXXXX.
.X....X.
.X.XX.X.
.X.XX.X.
.X.XX.X.
.X....X.
.XXXXXX.
........

contains two islands.

Your task is to read a map as input, and produce as output the number of islands contained in the map.

Input

The input consists of a line containing two positive integers h w, giving the height and width of the map. Each of h and w is less than or equal to 100. Following this are h lines of input, each containing exactly w characters, each character being an X (land) or a . (water).

Other than the space separating the integers h and w on the first line of input, there shall be no other space characters in the input file.

Output

The output shall consist of a single integer n on a line giving the number of islands contained in the map.

Sample Input 1

3 5
...XX
X.X.X
X.XXX

Sample Output 1

Sample Input 2

8 8
..X..XX.
.XX..X.X
.X...X.X
.XX..XXX
....X..X
...XXX..
...X.X..
XX.XXX..

Sample Output 2

Scoring

Your program will receive 100% for giving the correct number of islands as output. Any other output will receive 0%.