Counting Islands in a 2D Grid

Given a 2D grid composed of characters '1' (representing land) and '0' (representing water), your task is to count the number of islands. An island is defined as a group of horizontally or vertically connected '1's. You may assume that the grid is completely surrounded by water.

This problem can be solved using a depth-first search (DFS) or breadth-first search (BFS) algorithm. The DFS approach can be explained by the recurrence:

\(dfs(i, j)\) will mark the current cell and recursively call itself to mark its adjacent cells if they contain a '1'.

The expected time complexity is \(O(m \times n)\), where \(m\) and \(n\) are the dimensions of the grid.

inputFormat

The input is provided via standard input (stdin). The first line contains two integers \(m\) and \(n\) separated by a space, representing the number of rows and columns of the grid, respectively. The following \(m\) lines each contain a string of exactly \(n\) characters (each character is either '1' or '0') representing one row of the grid.

outputFormat

The output should be a single integer printed to standard output (stdout) representing the number of islands in the grid.

## sample

4 5
11000
11000
00100
00011

3

</p>