Number of Islands

You are given a 2D grid of characters representing a map, where '1' indicates land and '0' denotes water. An island is a group of adjacent lands connected horizontally or vertically. Your task is to compute the number of distinct islands in the grid.

Note: Diagonal connections do not count. That is, two lands are considered connected if and only if they are adjacent in one of the four primary directions (up, down, left, or right).

The solution should use an efficient algorithm such as Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the grid.

The formula for the DFS exploration can be expressed in LaTeX as follows:

$$DFS(i,j)=\begin{cases}\text{Mark } (i,j) \text{ as visited}\\ \text{and explore } DFS(i+1,j),\; DFS(i-1,j),\; DFS(i,j+1),\; DFS(i,j-1)\end{cases}$$

inputFormat

The input is received from stdin and is structured as follows:

• The first line contains two space-separated integers m and n representing the number of rows and columns of the grid respectively.
• The next m lines each contain n space-separated characters (each either '0' or '1') representing the grid.

For example:

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

outputFormat

Print a single integer to stdout which denotes the number of islands found in the grid.

## sample

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

3