CCO '03 P3 - Cube

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
2003 Canadian Computing Competition, Stage 2

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 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 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 solid pieces.

Input Specification

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, , and a blank line. The remaining lines will specify the horizontal layers of the cube from bottom to top. Each layer specification consists of an 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 on a line by itself.

Output Specification

For each cube given, in the order specified, print Yes if that cube is stable, and No if it is not.

Sample Input

2

AB
AB

BB
BA

3

AAA
BBB
AAA

AAA
ABA
AAA

ABA
ABA
ABA

0

Sample Output

No
Yes