Counting Distinct Islands in a Grid

You are given a grid of integers representing altitudes. Two cells are considered connected if they are adjacent vertically or horizontally and have the same altitude. An island is defined as a maximal group of connected cells with the same altitude.

Your task is to count the number of distinct islands in the grid.

In mathematical form, if the grid is represented as \( A \) of size \( n \times m \), then an island is a set of indices \( S \subseteq \{(i,j) : 0 \le i \lt n,\ 0 \le j \lt m\} \) such that for every \( (i,j) \in S \) and any \( (k,l) \) adjacent to \( (i,j) \) (i.e., \( |i-k|+|j-l|=1 \)), if \( A[i][j] = A[k][l] \) then \( (k,l) \in S \).

inputFormat

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

• The first line contains two space-separated integers \( n \) and \( m \) representing the number of rows and columns of the grid.
• Each of the next \( n \) lines contains \( m \) space-separated integers representing the altitudes of the cells.

If \( n = 0 \) or \( m = 0 \), the grid is empty.

outputFormat

Output a single integer to stdout: the number of distinct islands found in the grid.

2 2
1 1
1 1

1