Number of Islands

You are given a grid of size n × m consisting of characters '1' and '0', where '1' represents land and '0' represents water. An island is defined as a group of adjacent lands connected horizontally or vertically. Two cells are considered adjacent if they satisfy the condition $$|x_1 - x_2| + |y_1 - y_2| = 1$$.

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

Note: The grid is provided in the following format. The first line contains two integers n and m representing the number of rows and columns respectively, followed by n lines each containing a string of length m.

inputFormat

The input is read from stdin and is formatted as follows:

1. The first line contains two integers n and m, where 1 ≤ n, m ≤ 1000.
2. The next n lines each contain a string of m characters, representing the grid rows consisting only of the characters '1' and '0'.

outputFormat

Output a single integer to stdout which represents the number of islands in the grid.

3 3
111
010
111

1