pento
A pentomino is an arrangement of 5 squares grouped together along their sides. Each piece is associated with a code. There are 12 distinct pieces, illustrated in the image below, the associated code being written under each piece:
Pentominos can be combined (placed together) to create different shapes. In order to do this they can be turned (90, 180, 270 degrees) or mirrored. E.g. In the image below, the 12 pentominos are used to form a design similar to letter H.
Task
Being given such a shape, determine a method to obtain this shape using the 12 pentominos. The shape is given by a binary matrix with m lines and n columns, the 1 elements representing boxes that have to be "covered" with pentomino pieces, and the 0 elements representing free boxes that will not be covered.
We know that each pentomino can be used only once. Also, all the pieces will be utilized. Pieces cannot overlap. A problem solution will replace in the initial map the binary values with the codes of the pieces that cover each cell in particular.
Input Data
Line one of input file pento.in contains numbers m and n, separated by a single space, representing the size of the map. The following m lines each contain n binary digits, representing the map that has to be covered with pentominos.
Output Data
File pento.out will contain m lines, each line containing n positive integers between 0 and 12 representing the way in which the given map is covered.
Restrictions
Example
| pento.in |
pento.out |
Notes |
| 12 6 110011 110011 110011 111111 111111 111111 111111 111111 110011 111011 111011 111001 |
8 8 0 0 12 9 |
The solution corresponds to the shape of letter H in the task image. |
Time limit: 0.4 seconds/test
prof. Carmen Popescu
"Gheorghe Lazar" Sibiu National High School
Contact: popescu.carmen@yahoo.com