Counting Islands

You are given a grid of size (R \times C), where each cell is either '1' (land) or '0' (water). An island is defined as a group of connected lands connected horizontally or vertically (diagonal connections do not count).

The task is to count the number of islands in the grid. That is, count the number of connected components consisting of '1's. You may assume that all four edges of the grid are surrounded by water.

inputFormat

The first line contains two integers (R) and (C) representing the number of rows and columns respectively. Each of the next (R) lines contains (C) characters (either 0 or 1) separated by spaces.

outputFormat

Output a single integer representing the number of islands in the grid.## sample

4 5
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0

1