A frozen lake is modeled as a grid of R rows and C columns. Each cell is either ice (#) or open water (.). An ice floe is a maximal group of ice cells connected through shared edges: from an ice cell you may step to an ice cell directly above, below, to the left, or to the right (not diagonally).
Count the number of distinct ice floes.
Line 1: two integers R and C.
Next R lines: a string of exactly C characters each, using # for ice and . for water.
A single integer: the number of ice floes.
# or ..Example 1
Input
3 3 #.# .#. #.#
Expected
5
Explanation
The five ice cells sit at the four corners and the center, none sharing an edge with another, so each is its own floe: 5 floes.
Example 2
Input
3 3 ##. .#. ..#
Expected
2
Explanation
Cells (0,0),(0,1),(1,1) form one edge-connected floe; the ice cell at (2,2) touches nothing, giving a second floe: 2 floes.
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 →