Loading problem...
You are given an m × n binary matrix grid representing a topographical map where 1 represents land cells and 0 represents water cells. An island is defined as a group of land cells (1s) that are connected 4-directionally (horizontally or vertically adjacent). You may assume that all four edges of the grid are surrounded by water.
Two islands are considered geometrically equivalent if one can be transformed into the other through any combination of the following operations:
Your task is to determine the number of distinct island shapes present in the grid, where equivalence is determined by geometric transformations. In other words, islands that look the same after any sequence of rotations and/or reflections should be counted as a single distinct shape.
Key Concepts:
grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]1There are two islands in this grid. The first island (top-left corner) forms an L-shape, and the second island (bottom-right corner) also forms an L-shape. When we rotate the first island by 180 degrees clockwise, it matches the second island exactly. Since they are geometrically equivalent through rotation, there is only 1 distinct island shape.
grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]1Both islands form 2×2 squares. A square is symmetric under all rotations (90°, 180°, 270°) and reflections (horizontal, vertical). Therefore, both islands represent the same canonical shape, giving us 1 distinct island.
grid = [[1,0,1,0],[0,0,0,0],[1,1,0,1]]2This grid contains four single-cell islands (at positions (0,0), (0,2), (2,0), and (2,3)) plus one two-cell island at the bottom (cells (2,0) and (2,1)). Wait—let's recount: cells (0,0)=1, (0,2)=1, (2,0)=1, (2,1)=1, (2,3)=1. The cells (2,0) and (2,1) are horizontally adjacent forming one island. So we have: one 2-cell horizontal bar and three single-cell islands. Single cells are all equivalent (rotation/reflection doesn't change a point). The 2-cell bar is a different shape. Hence, 2 distinct shapes.
Constraints