After successfully planning the promenade, the Bandra Municipal Corporation is now turning its attention to the residential and commercial blocks nearby. The area has been divided into a map of m rows and n columns of plots, where each plot represents a building or an empty lot:
'B' → an existing building
'E' → an empty lot
A building cluster is a group of connected buildings that touch horizontally or vertically (diagonal adjacency does not count). The city edges are considered empty lots, so no cluster touches the boundary.
The municipal team wants to count how many separate building clusters exist in the area. This will help them plan road expansions, utilities, and green spaces around existing clusters, following the promenade redevelopment.
Essentially, this is the next step after handling reserved plots on the promenade — now the focus is understanding connectivity of existing buildings in the surrounding neighborhood.
Constraints
1 ≤ m, n ≤ 1000
1 ≤ m × n ≤ 10^6
Each character in the grid is either 'B' or 'E'
Input Format
The first line contains two integers m and n (1 ≤ m, n ≤ 1000) — the number of rows and columns in the grid.
The next m lines each contain a string of length n, where each character is either:
'B' — represents an existing building
'E' — represents an empty lot
Output Format
Print a single integer — the number of separate building clusters in the area.
Example 1
Input:
4 5
B B B E E
E E B B E
E E E E E
B B E E B
Output:
3
Explanation:
self explanatory
Log In to solve the Question