Number of Islands

You are given a grid representing a map where each cell is either '1' (land) or '0' (water). An island is defined as a group of adjacent lands connected horizontally or vertically. The grid is surrounded by water on all four edges.

Your task is to determine the number of islands in the grid.

The problem can be formally stated as follows:

Let (G) be an (R \times C) grid, where each cell (G[i][j]) is either '1' or '0'. An island is a maximal set of cells ({(i,j)}) such that for any two cells in the set, there exists a path connecting them using only horizontal or vertical moves through cells with value '1'.

For example, consider the grid below:

[ \begin{array}{ccccc} 1 & 1 & 0 & 0 & 0 \ 1 & 1 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 & 1 \end{array} ]

This grid contains 3 islands.

Good luck!

inputFormat

The input is read from standard input (stdin). The first line contains two integers (R) and (C) separated by a space, representing the number of rows and columns of the grid. This is followed by (R) lines, each containing (C) space-separated characters (either '1' or '0').

outputFormat

Output a single integer to standard output (stdout) representing the number of islands in the grid.## sample

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

3