Mid/Senior
Number of Distinct Islands
Given an m x n binary matrix grid, an island is a group of 1s connected horizontally or vertically. You may assume all four edges of the grid are surrounded by water.
Two islands are considered the same if and only if one island can be translated (shifted up, down, left, or right) to equal the other. Rotations and reflections are not considered the same shape.
Return the number of distinct island shapes in grid.
Example 1
1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1
Input
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]Output
1Both islands are 2 by 2 squares, so there is only one distinct island shape.
Example 2
1 1 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 1
Input
grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]Output
3The grid contains three distinct shapes: an L-shape, a horizontal two-cell island, and another L-like shape that is different by rotation/reflection rather than translation.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 50
- grid[i][j] is either 0 or 1