Reassembling the Glass Cow
Time limit5sMemory limit512 MB
Count the triples of scattered pieces that rebuild the colored figurine after rotation, reflection, and shifting.
- Level
Medium7 of 10
- Topics
- Brute force, Geometry, Matrix, Hash map
- Solved
- No attempts yet
Problem
Farmer John decided to decorate his house a little more. At a china shop he found a delicate glass cow figurine, and since it looked right for the mantelpiece he decided to buy it.
The figurine is written as an grid of characters, like the one below. A lowercase letter marks one part of the figurine, and different letters are different colors. The character . is an empty square.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa....
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
Just before he paid, a bull charged across the shop and smashed the figurine he wanted along with several others on the shelf. The cow figurine broke into three pieces, and they ended up mixed with the pieces scattered on the floor. A piece on the floor is written as a grid of characters in the same way.
A piece on the floor can lie flipped horizontally or vertically, or turned by a multiple of 90 degrees. You can move a piece, flip it, and turn it by multiples of 90 degrees. If three pieces placed this way do not overlap, cover every square of the figurine exactly once, and match every color, those three pieces rebuild the figurine.
Help Farmer John count how many combinations of three pieces out of the pieces on the floor rebuild the cow figurine.
Input
The first line contains one integer (). Then piece descriptions follow. The first description is the shape of the original cow figurine, and the next are the shapes of the pieces on the floor.
The first line of a piece description contains two integers and . Each of the next lines contains characters, one per square. Each character is a lowercase letter that names a color, or a . that marks an empty square. In the description of the original figurine, ; in the description of a piece on the floor, . Every piece is connected through shared edges and has at least one square that is not empty.
Output
Print the number of combinations of pieces , , () that rebuild the original figurine.
Note
In the example there are three combinations. They use pieces 0, 1, 2; pieces 0, 2, 4; and pieces 1, 3, 4. Pieces are numbered from 0.