Island Shapes Up to Symmetry

Hard

You are given a map chart of zeros and ones: 1 is land, 0 is water. An island is a group of land cells connected through their sides (horizontally or vertically; diagonal neighbours do not count). Everything outside the map is water. Two islands have the same shape if one can be laid over the other by a shift combined with a rotation by 90°, 180° or 270° and/or a mirror reflection. Return the number of distinct shapes among all the islands on the map.

Example 1

chart=[[1, 1, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 1, 0]] → 1

Both islands are four-cell corners: the lower one is the upper one rotated by 180°. One shape.

Example 2

chart=[[1, 1, 0, 1], [0, 1, 0, 1], [0, 0, 0, 1], [1, 0, 0, 0]] → 3

A three-cell corner, a three-cell vertical strip and a single cell are three different shapes: no rotation or reflection matches them.

Example 3

chart=[[1, 0, 1], [0, 0, 0], [1, 0, 1]] → 1

Constraints

1 ≤ len(chart), len(chart[0]) ≤ 50
All rows have the same length
chart[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Hash Table Hash Function

Similar problems

Distinct Island Shapes Medium One-Swap Word Families Hard Which Machine to Cure Hard Which Machine to Unplug Hard Merge Contact Cards Medium

Input

chart=[[1, 1, 1, 0], [0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0], [1, 1, 1, 0]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 80 tests on the server, hidden ones included.