Count the Number of Islands

Given a 2D grid map consisting of '1's (representing land) and '0's (representing water), your task is to count the number of islands. An island is defined as a group of adjacent lands connected horizontally or vertically (diagonal connections do not count), and is completely surrounded by water.

Note: The borders of the grid are assumed to be surrounded by water.

You can model the connectivity using the standard Depth-First Search (DFS) or Breadth-First Search (BFS) algorithm. Mathematically, if we denote the cell at row i and column j as \(a_{i,j}\), then two cells \(a_{i,j}\) and \(a_{k,l}\) are adjacent if and only if \(|i-k|+|j-l|=1\). The problem is to find the number of connected components made up of cells with value '1'.

inputFormat

The input is read from standard input (stdin) and has the following format:

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

outputFormat

Output a single integer to standard output (stdout) representing the number of islands found in the grid.

4 5
11000
11000
00100
00011

3