A patch of night sky is a grid of R rows and C columns. Each cell is either a star (*) or empty (.). Two stars belong to the same constellation cluster if one can be reached from the other by repeatedly stepping to a star in any of the eight surrounding cells (horizontally, vertically, or diagonally adjacent).
Count the number of distinct constellation clusters.
Line 1: two integers R and C.
Next R lines: a string of exactly C characters each, using * for a star and . for empty sky.
A single integer: the number of constellation clusters.
* or ..Example 1
Input
3 3 *.* .*. *.*
Expected
1
Explanation
The center star is diagonally adjacent to all four corner stars, joining every star into one cluster: 1.
Example 2
Input
3 3 *.. ..* *..
Expected
3
Explanation
None of the three stars are within one step (even diagonally) of another, so there are 3 clusters.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →