Pond Count


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
Python

Farmer John has a rectangular piece of land of size N*M.

Recently, due to rainfall, some parts of the land have been flooded.

The land is now represented by a character matrix.

In each cell, if it contains rainwater, it is represented by 'W'; if it does not contain rainwater, it is represented by '.'.

Now, John wants to know how many ponds have formed in his land.

Each connected set of water-filled cells can be considered as one pond.

Each cell is considered to be connected to its eight neighboring cells: up, down, left, right, up-left, up-right, down-left, and down-right.

Please output the total number of ponds, i.e., how many connected 'W' blocks exist in the matrix.

Input format
The first line contains two integers N and M.

The next N lines each contain M characters, which are either 'W' or '.', representing the water accumulation status of the rectangular land. There are no spaces between the characters.

Output format
Output an integer, representing the number of ponds.

Data range
1 ≤ N, M ≤ 1000

Sample input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample output

3

Comments

There are no comments at the moment.