Bull in a China Shop (Platinum)#10578
Farmer John has decided that his home needs some additional decoration. While visiting a local china shop, he finds a delicate glass cow figurine that he decides to purchase, knowing that it will fit perfectly on the mantel above his fireplace.
The shape of the cow figurine is described by an n \times m~(3 \le n, m \le 500) grid of characters, like the one shown below. Lowercase letters represent cells that are part of the figurine, with different letters indicating different colors, while '' characters represent empty cells.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............Unfortunately, just before FJ can make his purchase, a bull runs through the shop and breaks not only FJ's figurine, but many of the other glass objects on the shelves as well! FJ's figurine breaks into pieces, which quickly become mixed in with total pieces lying on the floor. Each of the pieces is described by a grid of characters, just like the original figurine.
Please help FJ determine how many sets of pieces, chosen from the pieces on the floor, could be glued back together to reconstruct his broken figurine.
The pieces on the floor may have been flipped horizontally or vertically, or rotated by any multiple of degrees. Given the original grid and the grids describing the pieces, your task is to find all sets of pieces that can be joined together to form the original picture. The pieces may be translated, flipped, or rotated by any multiple of degrees.
When the three pieces are superimposed, they must exactly form the original picture: every colored cell in the original picture must be represented by exactly one of the three pieces, with no missing or overlapping cells.
The first line contains a single integer k~(4 \le k \le 100). This is followed by k + 1 piece descriptions. The first description is the original glass cow, and the following descriptions are the broken pieces.
Each description begins with a line containing two integers and c~(1 \le r, c \le 100). The following lines contain lowercase alphabetic characters describing the color of each cell. Each piece is horizontally and vertically connected and contains at least one non-empty cell.
Print the number of triples i, j, k~(i < j < k) such that pieces , and can be arranged to form the original glass cow.
The three solutions use the following sets of pieces: (0, 1, 2), (0, 2, 4), and (1, 3, 4).
Example 1