Distinct Islands

Given a grid of integers representing land (1) and water (0), an island is defined as a group of adjacent land cells connected vertically or horizontally. Two islands are considered identical if one can be translated (without rotation or reflection) to coincide with the other, i.e. they have the same shape.

Your task is to count the number of distinct islands in the grid. The shape of an island can be represented by the relative positions of its cells with respect to the top-leftmost cell in that island.

For example, consider the grid below:

1 1 0 0 0
1 1 0 0 1
0 0 0 1 1
0 0 0 1 1

There are two distinct island shapes in the grid.

inputFormat

The first line contains two integers R and C, representing the number of rows and columns in the grid.

Each of the next R lines contains C space-separated integers (either 0 or 1), representing the grid.

outputFormat

Output a single integer, which is the number of distinct islands in the grid.

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

2