Standard Bar Graphs · Traversal Problems O(n * m) · O(n * m)
A city planner scans a zoning map where built lots (1) form clusters separated by empty land (0). Two clusters built on the same footprint — same relative shape, regardless of where they sit on the map — count as one design. The planning office needs the number of distinct designs present, rotations and reflections counting as different designs.
Input: An n x m binary grid where 1 marks a built lot and 0 empty land.
Output: Return the number of distinct island shapes, where two islands are identical only if one translates exactly onto the other.
1 <= n, m <= 500grid[i][j] is 0 or 1Input: {"grid":[[1,1,0],[0,0,0],[1,1,0]]}
Output: 1
Both clusters are the same 2x1 domino footprint, one row apart.
Input: {"grid":[[1,1,0],[1,0,0],[0,0,1]]}
Output: 2
An L-shaped cluster and a single-lot cluster are two different designs.