Number of Islands

You are given a 2D grid map of '1's (land) and '0's (water). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

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

Note: Two cells are considered connected if they are adjacent vertically or horizontally (not diagonally). The input grid can be empty.

For example, given the grid:

4 5
11110
11010
11000
00000

There is only 1 island.

The problem can be mathematically modeled as: given a grid \(G\) of size \(m \times n\), count the number of connected components where each component is defined by adjacent cells with value '1'.

inputFormat

The first line contains two integers \(m\) and \(n\) representing the number of rows and columns of the grid, respectively.

Each of the next \(m\) lines contains a string of length \(n\) comprising only characters '1' (land) and '0' (water). These \(m\) lines represent the grid.

Input is taken from standard input (stdin).

outputFormat

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

## sample

4 5
11110
11010
11000
00000

1

</p>