Counting Islands in a Binary Grid

You are given an m x n binary grid that represents a map of '1's (land) and '0's (water). An island is a maximal group of horizontally or vertically connected '1's. Your task is to count the number of islands in the grid.

Note: Two cells are considered connected if they are adjacent horizontally or vertically (not diagonally).

The number of islands is defined as follows. For a given grid \(G\), iterate over each cell. If the cell contains '1' and has not been visited yet, perform a depth-first search (DFS) or breadth-first search (BFS) to mark all connected '1's. Each such search corresponds to one island.

inputFormat

The input is received from standard input (stdin) and is formatted as follows:

1. The first line contains two space-separated integers \(m\) and \(n\), indicating the number of rows and columns of the grid respectively.
2. This is followed by \(m\) lines, each containing a string of \(n\) characters where each character is either '0' (water) or '1' (land).

outputFormat

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

## sample

4 5
11110
11010
11000
00000

1

</p>