Number of Islands

You are given a 2D grid representing a map of '1's (land) and '0's (water). An island is defined as a group of adjacent lands connected horizontally or vertically. Diagonally adjacent cells are not considered connected. Your task is to count the number of islands in the given grid. The boundaries of the grid are surrounded by water.

The problem can be formally described as follows:

Given an \( m \times n \) matrix, where each element is either '1' or '0', find the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

For example, consider the grid:

[ ["1", "1", "1", "1", "0"], ["1", "1", "0", "1", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "0", "0", "0"] ]

There is only one island. In another example:

[ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"] ]

There are three islands.

inputFormat

The input is given via standard input (stdin). The first line contains two integers \( m \) and \( n \) which denote the number of rows and columns in the grid respectively. This is followed by \( m \) lines, each containing \( n \) space-separated characters ('0' or '1'). If \( m = 0 \) or \( n = 0 \), the grid is empty.

outputFormat

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

## sample

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

1