Number of Islands

You are given a 2D grid (or matrix) of integers where each cell is either 0 or 1. A cell with a value of 1 represents land and a cell with a value of 0 represents water. An island is defined as a group of adjacent 1s connected horizontally or vertically (not diagonally). Your task is to count the number of distinct islands in the matrix.

For two cells with coordinates \( (i,j) \) and \( (k,l) \), they are considered adjacent if \( |i-k|+|j-l|=1 \). Use a depth-first search (DFS) based method to traverse the grid and count the islands.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

n m
row1
row2
...
rown

Where n is the number of rows and m is the number of columns. Each of the following n lines contains m space-separated integers (either 0 or 1) representing a row of the matrix.

outputFormat

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

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

3