2003 Canadian Computing Competition, Stage 2
Day 1, Problem 3: Cube
Imagine a cube formed from solid interlocking pieces of various shapes. If the pieces are sufficiently entwined, the only way to separate them would be to cut some of them. We can ask the question: "is the cube stable?" That is, is it physically impossible to separate the cube into 2 or more fragments without deforming or cutting any individual piece?
Your program must answer this question for a variety of such cubes.
The pieces that make up a cube will be specified as follows: divide the cube into a grid of n * n * n miniature cubes, each labeled by a capital letter. Two adjacent (face-sharing) minicubes are joined together if and only if they are labeled by the same letter. For instance, the first example cube given consists of 3 solid pieces.
Your program will be given the specification of up to 10 different cubes. The first two lines of each specification will consist of the size of that cube, n (1 ≤ n ≤ 10), and a blank line. The remaining n * (n + 1) lines will specify the n horizontal layers of the cube from bottom to top. Each layer specification consists of an n * n square showing the labels for each minicube on that layer, followed by a blank line. There will be no spaces in the input. The input will be terminated by the number 0 on a line by itself.
For each cube given, in the order specified, print "Yes" if that cube is stable, and "No" if it is not.
2 AB AB BB BA 3 AAA BBB AAA AAA ABA AAA ABA ABA ABA 0
Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 28, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3