Count Distinct Island Shapes in a Binary Grid

You are given an m x n binary grid grid, where grid[i][j] is either 0 (water) or 1 (land).

An island is a maximal group of 1-cells connected 4-directionally (up, down, left, right). Diagonal adjacency does not connect cells.

Two islands are considered to have the same shape if and only if one island can be translated (shifted horizontally and/or vertically, without rotating or reflecting) so that it exactly coincides with the other island, cell for cell.

Return the number of distinct island shapes in the grid.

Input

• grid: a list of m rows, each a list of n integers, each 0 or 1.

Output

• A single integer: the count of distinct island shapes.

Constraints

• 1 <= m, n <= 50
• grid[i][j] is 0 or 1

Edge cases your solution must handle correctly

• A grid containing no 1-cells (the answer is 0).
• Single-cell islands: all 1x1 islands share one shape regardless of position.
• Islands touching the grid border.
• Multiple islands with identical shapes located at different positions (they count once).
• A grid completely filled with 1s (one island, one shape).

Example 1

grid = [
 [1, 1, 0, 0, 0],
 [1, 0, 0, 0, 0],
 [0, 0, 0, 1, 1],
 [0, 0, 0, 0, 1]
]

Output: 2

There are two islands. The first occupies relative cells {(0,0), (0,1), (1,0)} and the second {(0,0), (0,1), (1,1)}. No translation maps one onto the other (rotations/reflections are not allowed), so there are 2 distinct shapes.

Example 2

grid = [
 [1, 1, 0, 1, 1],
 [1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 1, 1, 0, 0],
 [0, 1, 0, 0, 0]
]

Output: 1

All three islands are the same L-shaped triomino translated to different positions, so there is exactly 1 distinct shape.

Example 3

grid = [
 [0, 0],
 [0, 0]
]

Output: 0

There are no islands.