Counting Islands

You are given a 2D grid that represents a map of 0s (water) and 1s (land). An island is defined as a group of adjacent lands connected horizontally or vertically (not diagonally). The task is to count the number of islands present in the grid.

More formally, an island is a maximal set of grid cells such that:

\( \text{cell}_{ij} \text{ is part of the island if } grid[i][j]=1 \text{ and } \exists\text{ a path connecting } grid[i][j] \text{ to some other cell with value } 1 \text{ using only horizontal and vertical moves} \).

You can use either depth-first search (DFS) or breadth-first search (BFS) to solve the problem.

inputFormat

The input is given via standard input (stdin) in the following format:

• The first line contains two space-separated integers \( r \) and \( c \) representing the number of rows and columns, respectively.
• The next \( r \) lines each contain a binary string of length \( c \) consisting of the characters '0' and '1', representing the grid.

You can assume that \( 1 \leq r, c \leq 500 \).

outputFormat

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

1 1
1

1