Unique Shapes
Time limit2sMemory limit1024 MB
Count the number of distinct polyominoes (free polyominoes) that can be formed from exactly 8 unit squares, where shapes matching under rotation, translation, or reflection count as one.
- Level
Easy3 of 10
- Topics
- Brute force, Backtracking, Geometry, Implementation
- Solved
- No attempts yet
Problem
Imagine you have a lot of square blocks, and you can put them together into different shapes. You can make all kinds of shapes. How many of them are truly unique?
A shape is a connected group of blocks placed on a regular grid, where each block is connected to another block above it, below it, to its left, or to its right. Two shapes are considered unique if there is no sequence of rotations, translations, or reflections that can cause them to be identical.
With one block, only one unique shape can be made. With two blocks, the same is true. With three blocks, two unique shapes are possible, and with four blocks, five unique shapes are possible. The figure below gives illustrations of these cases:
Input
There is no input for this problem.
Output
Print out the number of unique shapes that can be constructed using 8 square blocks, as a decimal integer.