Number of Islands

You are given a 2D grid of characters where each cell is either '1' (representing land) or '0' (representing water). An island is defined as a group of adjacent lands connected horizontally or vertically (diagonal connections do not count). The grid is surrounded by water on all four edges.

Your task is to compute the total number of islands in the given grid.

Note: Two cells are considered connected if they are adjacent in the up, down, left, or right direction. Mathematically, if we index the grid as \( grid[i][j] \), then two cells \( grid[i][j] \) and \( grid[k][l] \) are adjacent if \(|i-k|+|j-l|=1\).

inputFormat

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

r
row_1
row_2
...
row_r

Here, the first line contains a single integer r indicating the number of rows in the grid. Each of the following r lines is a string consisting only of characters '1' and '0', representing one row of the grid.

outputFormat

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

4
11110
11010
11000
00000

1