461. Number of Distinct Islands
You are given an m × n grid of characters where '1' is land and '0' is water. An island is a maximal group of land cells connected up, down, left, or right (never diagonally).
Two islands have the same shape when one can be slid — translated only, with no rotation and no mirror flip — so that it lies exactly on top of the other. Return the number of distinct island shapes in the grid.
Example 1:
Input: grid = ["11000", "11000", "00011", "00011"]
Output: 1
Explanation: There are two islands, but both are 2×2 squares — sliding one onto the other matches perfectly, so there is only one distinct shape.
Example 2:
Input: grid = ["11011", "10000", "00001", "11011"]
Output: 3
Explanation: Four islands: an L of three cells (top left), two horizontal dominoes (top right and bottom left) that share a shape, and a bent three-cell piece (bottom right) that is a flipped L — flips don't count as equal, so shapes are L, domino, bent piece: 3.
Constraints:
- 1 ≤ m, n ≤ 50
- grid[i][j] is '0' or '1'
Hints:
Flood fill (DFS/BFS) already separates the islands. The real question is how to decide that two islands 'look alike' — shape must ignore *where* the island sits, so describe each island in position-independent terms.
Give every island a canonical signature and count distinct signatures with a hash set. Two classic signatures: the set of cell offsets relative to the island's first-visited cell, or the DFS path string — the sequence of directions taken, with an extra marker written on every backtrack.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: grid = ["11000", "11000", "00011", "00011"]
Expected output: 1