Loading problem...
You are provided with a two-dimensional binary matrix grid of dimensions m x n, where each cell contains either 1 (representing land) or 0 (representing water). A landmass (or island) is defined as a contiguous region of land cells connected horizontally or vertically (4-directional connectivity). You may assume that all cells outside the grid boundaries are water.
Two landmasses are considered to have the same shape if and only if one can be translated (shifted horizontally and/or vertically) to perfectly overlap the other. Importantly, rotation and reflection (mirroring) do not make two landmasses identical—only pure translation counts.
Your task is to determine and return the total count of distinct landmass shapes present in the grid.
Key Insight: To identify whether two landmasses share the same shape, you must normalize their representation. One effective approach is to record the relative positions of all land cells within each landmass with respect to a consistent reference point (such as the top-left cell or the first cell discovered during traversal). Landmasses with identical normalized representations are considered duplicates.
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]1The grid contains two separate 2x2 square landmasses. Since one can be translated to exactly match the other (they have the same shape), there is only 1 unique landmass shape.
grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]3This grid contains multiple landmasses with different shapes. After analyzing the shape of each landmass by normalizing their cell positions, we find that there are exactly 3 distinct shapes among all the landmasses present.
grid = [[1,0,0,1,1],[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,1]]3The grid features several landmasses scattered across different positions. By extracting and normalizing the shape signature of each landmass, we determine that 3 unique geometric patterns exist, regardless of their absolute positions in the grid.
Constraints