You are given a rectangular map made of land cells (1) and water cells (0). An island is a maximal group of land cells connected horizontally or vertically (not diagonally). Water separates islands.
Count how many distinct islands the map contains.
Input format
Line 1: two integers rows and cols.
Next rows lines: each a string of exactly cols characters, every character being 0 (water) or 1 (land), with no spaces between them.
Output format
A single integer: the number of islands. If there is no land at all, the answer is 0.
Constraints
- 1 ≤ rows ≤ 300
- 1 ≤ cols ≤ 300
- Each grid character is
0or1. - Cells are adjacent only in the 4 cardinal directions (up, down, left, right).