Count the Distinct Island Shapes
Implement countDistinctShapes
You are given a grid of land (1) and water (0). Two islands have the same shape when one can be slid (without rotating or flipping) onto the other. Count how many different shapes of islands the grid contains.
Counting islands is a plain flood fill; the extra work is to turn each island into something comparable, such as a list of offsets from its first cell or a string that records how a depth-first search walks around it.
Example 1:
Input: grid = [[1,1,0,1,1],[1,0,0,1,0],[0,0,0,0,0],[0,1,0,0,1]]
Output: 2
Example 2:
Input: grid = [[1,0,1]]
Output: 1
Example 3:
Input: grid = [[1,1,0],[0,0,0],[1,0,0],[1,0,0]]
Output: 2
+ 12 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 12; grid[r][c] is 1 (land) or 0 (water) - ●
An island is a group of land cells connected through shared sides - ●
Two islands have the same shape when one can be moved (translated) onto the other; rotating or mirroring an island makes a different shape - ●
Return the number of distinct island shapes
grid =
[[1,1,0,1,1], [1,0,0,1,0], [0,0,0,0,0], [0,1,0,0,1]]