Baltic OI '10 P2 - Lego

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type
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 (2 \times 2 "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 6 \times 6 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

1 \le H \le 6

Input Specification

The first line of input contains H, the height of the construction. The following H lines contain 6 characters on each line, giving a side view of the construction (marked A on the figure below). The j^\text{th} character on the i^\text{th} line specifies what you see looking at the j^\text{th} column from the left on the i^\text{th} 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 H lines with the construction seen from an angle where the observer has moved 90 degrees counterclockwise around the construction (marked B 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 6 possible constructions that satisfy the input.

Comments


  • 0
    d  commented on Dec. 3, 2022, 11:34 p.m.

    On the test data, the answer always fits in a 64-bit integer.