A geological scan produces a grid of rows by cols cells. Each cell is either empty (0) or contains a mineral deposit (1). Two deposit cells belong to the same cluster if they are adjacent — including diagonally (up, down, left, right, and all four diagonal directions all count as adjacent).
Count the number of distinct deposit clusters.
Line 1: two integers rows and cols.
Next rows lines: a string of exactly cols characters, each 0 or 1.
A single integer: the number of 8-directionally connected clusters of 1 cells.
Example 1
Input
3 3 100 010 001
Expected
1
Explanation
The three 1s form a diagonal chain (0,0)-(1,1)-(2,2), all diagonally adjacent, so it is one cluster.
Example 2
Input
2 2 10 01
Expected
1
Explanation
(0,0) and (1,1) are diagonally adjacent, forming a single cluster of size 2.
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 →