grid is a map where 1 is land and 0 is water. An island is a maximal group of land cells
connected up, down, left or right. Two islands have the same outline if one can be slid (moved
without rotating or flipping) so that it covers exactly the cells of the other.
Return the number of different outlines among all islands.
Examples
Input: grid = [[1,1,0,1,1],
[1,0,0,1,0],
[0,0,0,0,0],
[0,1,1,0,1]]
Output: 3
Explanation: the two L-shapes at the top are slides of each other; the
domino (3,1)-(3,2) and the single cell (3,4) are two more outlines.
Input: grid = [[1,0],
[0,1]]
Output: 1
Explanation: two single cells.
Input: grid = [[0]]
Output: 0
Constraints
1 <= rows, cols <= 60- Rotated or mirrored copies count as different outlines.
- Target
O(rows * cols)time (plus the cost of hashing the shapes).
Goals
- Collect the cells of each island with a flood fill
- Normalise a shape so that translated copies compare equal
- Count distinct shapes with a set of hashable signatures