Count Islands

You are given a two-dimensional grid of characters where each character is either '0' representing water or '1' representing land. Two land cells are considered to be part of the same island if they are horizontally or vertically adjacent.

Your task is to count the number of distinct islands in the grid. Formally, if we denote the grid by \(grid\) of size \(n \times m\), then two cells \((i, j)\) and \((k, l)\) belong to the same island if and only if \(|i-k| + |j-l| = 1\) or there exists a sequence of adjacent land cells connecting them.

Input/Output Format:

The input is given via standard input and the output should be printed to standard output.

inputFormat

The first line contains two space-separated 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\) composed solely of characters '0' and '1', representing each row of the grid.

outputFormat

Output a single integer denoting the number of islands in the grid.

4 5
11110
11010
11000
00000

1