ZOJ Problem Set - 2669
Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyminoes. Polymino is usually represented as a set of sidewise connected squares. Polymino with n squares is called n-polymino.
In this problem you are to find a number of distinct free n-polyminoes that fit into rectangle w * h. Free polyminoes can be rotated and flipped over, so that their rotations and mirror images are considered to be the same.
For example, there are 5 different pentaminoes (5-polyminoes) that fit into 2 * 4 rectangle and 3 different octominoes (8-polyminoes) that fit into 3 * 3 rectangle.
There are several test cases in the input. Each case consists of a single line with 3 integer numbers n, w, and h (n ≤ 10, 1 ≤ w, h ≤ n).
Write to the output file a single integer number --- the number of distinct free n-polyminoes that fit into rectangle w * h.
5 1 4
Source: Northeastern Europe 2004