Counting Connected Groups in a Grid

You are given a 2-dimensional grid of size \(N \times M\) consisting of integers \(0\) and \(1\). Your task is to count the number of connected groups (components) of cells that contain \(1\). Two cells are considered connected if they are adjacent horizontally or vertically (i.e. up, down, left, or right). Note that if the grid is empty (i.e. \(N = 0\) or \(M = 0\)), the answer is \(0\).

Input Format: The first line contains two integers \(N\) and \(M\). Then \(N\) lines follow, each containing \(M\) integers separated by spaces representing the grid.

Output Format: Output a single integer which is the number of connected groups of \(1\)'s in the grid.

inputFormat

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

N M
row_1
row_2
... 
row_N

Here, each row_i consists of M space-separated integers (either 0 or 1). If \(N = 0\) or \(M = 0\), the grid is considered empty.

outputFormat

Output to stdout a single integer: the number of connected groups of 1's in the grid.

5 6
0 1 0 0 0 1
0 1 1 0 1 0
0 0 0 0 1 1
1 0 0 1 1 0
1 1 0 0 0 0

4