Count distinct island shapes in a grid

Problem Statement

Given a 2D grid of 0s (water) and 1s (land), an island is a group of 1s connected 4-directionally. Two islands are considered the same if one island can be translated to match the other exactly (they have the same shape and size).

Write a function count_distinct_islands(grid) that returns the number of distinct island shapes in the grid.

Function Signature

def count_distinct_islands(grid: list[list[int]]) -> int:

Examples

Example 1: Input:

[[1, 1, 0],
 [1, 0, 0],
 [0, 0, 1]]

Output: 2 Explanation: The first island is defined by the shape of the top-left 1s; the second is a single 1 at the bottom right.

Example 2: Input:

[[1, 1, 0, 1, 1],
 [1, 0, 0, 1, 0]]

Output: 2 Explanation: Even though the islands are in different locations, the two shapes are structurally identical.

Constraints

• grid dimensions are up to 50x50.
• grid[i][j] is 0 or 1.

Edge Cases

• Empty grid.
• Grid with no land.
• Grid where all land pieces are connected.

Implementation Details

To represent an island, you can record the path taken during a traversal (e.g., 'up', 'down', 'left', 'right') relative to the starting cell of that specific island. Ensure you mark visited cells to avoid counting them multiple times.