Counting Islands

The task is to count the number of islands in a grid. An island is defined as a group of connected land cells. Two cells are considered connected if they are adjacent horizontally or vertically. In the grid, a cell with a value of '1' represents land and a cell with a value of '0' represents water. The input starts with two integers, n and m, that specify the number of rows and columns respectively, followed by n lines each containing a string of m characters.

The problem can be mathematically formulated as follows: Let \( G \) be a grid of size \( n \times m \) where each \( G_{i,j} \) is either 0 or 1. An island is a set of positions \( S \subseteq \{(i,j)\} \) such that for every \( (i,j) \in S \), \( G_{i,j} = 1 \), and every two adjacent cells in \( S \) (i.e. cells that share an edge) are connected.

Your task is to determine the total number of such islands.

inputFormat

The first line contains two integers n and m, representing the number of rows and columns in the grid. Each of the next n lines contains a string of m characters (each character is either '1' or '0').

outputFormat

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

4 5
11000
11000
00100
00011

3