Number of Distinct Islands

Given a rectangular binary grid, an island is a maximal group of land cells (1) connected up, left, down or right. Two islands have the same shape exactly…

Given a rectangular binary grid, an island is a maximal group of land cells (1) connected up, left, down or right. Two islands have the same shape exactly when translating one produces the other. Rotation and reflection do not count as equality. Return the number of distinct island shapes.

1 <= N, M <= 500; cells are integers 0 or 1. Visual presets are limited to 6×6.

Example 1: input grid = [[1,0,0],[0,1,1],[0,0,0]]; output 2. Diagonal contact does not connect the singleton at (0, 0) to the horizontal two-cell island. These are two different shapes.

Example 2: input grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]; output 3. The grid contains two differently oriented three-cell L shapes and two translated horizontal pairs. The pairs share one shape, giving three distinct shapes in total.

Category: Graphs. Topic: graph. Difficulty: Medium. Patterns: graph-traversal.