Count the Connected Regions in a Binary Grid

You are given a binary grid of size M × N containing only 0’s and 1’s. A cell with value 1 is considered connected to its 8 neighbors (i.e. horizontal, vertical, and diagonal connections).

Your task is to calculate the number of distinct connected regions consisting entirely of 1’s. Two cells belong to the same region if they are connected directly or indirectly via 8-direction adjacency.

Read the grid from standard input and write the result to standard output.

Note: Use \(8\)-direction connectivity, which means that even diagonal neighbors are considered adjacent.

inputFormat

The first line contains two space-separated integers M and N representing the number of rows and columns of the grid.

The next M lines each contain N integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

Output a single integer which is the number of distinct connected regions of 1’s in the grid.

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

3