Counting Islands in a Grid

You are given a grid of size \( n \times m \) consisting of characters '0' and '1'. Each '1' represents a part of the land and each '0' represents water. An island is formed by connecting adjacent lands horizontally or vertically.

Your task is to count the number of distinct islands in the grid.

Note: Two cells are considered adjacent if they share a common edge. Diagonal connections do not count.

For example, given the grid:

4 5
11000
11000
00100
00011

There are 3 islands. One island is formed by the top-left block, one island by the isolated '1' in the middle, and the last island by the two connected '1's at the bottom-right.

The solution involves using depth-first search (DFS). Use the DFS algorithm to explore all connected components starting from each unvisited land cell.

The mathematical idea behind the DFS on the grid is to recursively visit all neighbors of a cell if they are land. The recurrence can be formalized as:

\[ DFS(i, j) = \begin{cases} \text{mark } (i,j) \text{ visited} & \text{if } grid[i][j] = 1 \\ DFS(i+1, j) + DFS(i-1, j) + DFS(i, j+1) + DFS(i, j-1) & \text{for each adjacent cell} \\ 0 & \text{if } grid[i][j] = 0 \text{ or out of bounds} \end{cases} \]

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of rows and columns of the grid respectively. The following \( n \) lines each contain a string of length \( m \) consisting of characters '0' and '1'.

outputFormat

Output a single integer which is the number of islands in the grid.

## sample

4 5
11000
11000
00100
00011

3