Count Distinct Islands

You are given a 2D grid of integers representing a map, where 1 indicates land and 0 indicates water. An island is a group of connected 1's (land) connected vertically or horizontally. Your task is to count the number of distinct islands in the grid.

If the grid is empty, the answer is 0.

The connectivity is defined by the four cardinal directions. In mathematical terms, if we index the grid from 0, two cells (i,j) and (k,l) are connected if and only if \( |i-k|+|j-l| = 1 \).

inputFormat

The first line of input contains two integers r and c (r \(\ge\) 0, c \(\ge\) 0) representing the number of rows and columns in the grid respectively.

If r is 0, then the grid is considered empty.

The next r lines each contain c space-separated integers (either 0 or 1) representing the grid.

outputFormat

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

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

4