Distinct Islands

You are given a grid with n rows and m columns. Each cell in the grid contains either a 0 (representing water) or a 1 (representing land). An island is a group of connected 1's where connectivity is defined as horizontal or vertical (not diagonal).

Two islands are considered distinct if and only if one island's shape cannot be translated (i.e., shifted horizontally and/or vertically) to exactly match the other island's shape. Formally, if for an island the collection of cell coordinates is given by \[ S = \{ (x,y) \}\n\] then its normalized shape can be expressed as \[ S' = \{ (x - x_0, y - y_0) \mid (x,y) \in S \}\n\] where \((x_0,y_0)\) is the coordinate of a reference cell in the island (for example, the top-left most cell of the island). Two islands are considered the same if their normalized sets \(S'\) coincide.

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

inputFormat

The input is read from standard input (stdin). The first line contains two space-separated integers n and m, representing the number of rows and columns of the grid, respectively. Each of the following n lines contains m space-separated integers (either 0 or 1) representing the grid.

Input Format:

n m
grid[0][0] grid[0][1] ... grid[0][m-1]
... 
grid[n-1][0] grid[n-1][1] ... grid[n-1][m-1]

outputFormat

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

4 4
1 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0

1