Counting Islands in a Grid

You are given a 2D grid of size \(n \times m\) consisting of 0s and 1s, where 1 represents land and 0 represents water. Your task is to count the number of islands, where an island is defined as a group of horizontally or vertically adjacent 1s. Diagonal connections do not count.

Note: An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Input and output are provided via standard input and output respectively.

inputFormat

The first line of the input contains two integers \(n\) and \(m\) - the number of rows and columns of the grid.

Then follow \(n\) lines, each containing \(m\) space-separated integers (either 0 or 1) representing the grid.

outputFormat

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

4 5
1 1 1 1 0
1 1 0 1 0
1 1 0 0 0
0 0 0 0 0

1