Baltic Olympiad in Informatics: 2010 Day 1, Problem 2
You are using Lego building blocks to train an artificial vision system. Write a program that, given pictures of a Lego construction taken from two angles, calculates in how many different ways it can be built.
In this task, there is only one kind of lego block ( "knobs", see picture below), but it
can have three different colors: white W
, gray G
or black B
. All blocks exist in unlimited
amounts. You use a square base with knobs. Every block must have its edges parallel
to this base and no block may extend outside of it. Every block must rest upon at least one
underlying block.
Left: An allowed way to place a block on top of another one. Center: An illegal way (the upper block hangs in the air). Right: Another illegal way (the upper block extends outside the base).
Constraints
Input Specification
The first line of input contains , the height of the construction. The following lines contain characters on each line, giving a side view of the construction (marked on the figure below). The character on the line specifies what you see looking at the column from the left on the row or layer.
Each character may be one of W
, G
, B
or .
, specifying a color or a hole .
. Note that you
cannot estimate the depth, so a color seen in a certain position may either belong to a block
near the front edge, or further back, provided no other block is blocking the sight.
The first side view is followed by second set of lines with the construction seen from an angle where the observer has moved degrees counterclockwise around the construction (marked on the figure below).
Output Specification
Your program should output one integer: the number of different Lego constructions that satisfy the side views given. Note that even if two different possible constructions could be obtained from each other by rotating or mirroring, they both should be counted.
Sample Input
2
WWGG..
.BB.WW
.WGG..
WWGG..
Sample Output
6
Explanation
One of the possible constructions that satisfy the input.
Comments
On the test data, the answer always fits in a 64-bit integer.