Counting Islands

You are given a grid of size \(R \times C\) represented by integers. The integer 1 represents land and 0 represents water. An island is defined as a group of adjacent lands connected horizontally or vertically. Your task is to count the number of islands in the grid.

The problem can be formulated as follows: Given a grid \(G\) where \(G_{i,j}\) is either 0 or 1, an island is a maximal set of cells \(\{(i,j)\}\) such that each cell contains 1 and every two cells in the set are connected by a path through adjacent 1's. In mathematical notation, find the number of connected components in \(G\) based on the neighborhood relation defined as:

[ (i_1,j_1) \sim (i_2,j_2) \iff |i_1 - i_2| + |j_1 - j_2| = 1. ]

Read the grid from standard input and output the number of islands to standard output.

inputFormat

The first line of input contains two integers \(R\) and \(C\) separated by a space, representing the number of rows and columns respectively. Each of the following \(R\) lines contains \(C\) integers (either 0 or 1) separated by spaces, representing the grid.

Example:

5 5
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 1 1 0 0

outputFormat

Output a single integer representing the number of islands detected in the given grid.

5 5
1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 0 0
1 1 1 0 0

3