Cube
Time limit1sMemory limit128 MB
Given an n by n by n grid of letters, decide whether the connected same-letter pieces can be pulled apart without cutting, meaning no single piece separates the cube.
- Level
Hard8 of 10
- Topics
- Graph, DFS, Geometry, Implementation
- Solved
- No attempts yet
Problem
Imagine a large cube built from solid, interlocking pieces of various shapes. If the pieces are entangled enough, the only way to pull them apart might be to cut some of them. We can ask: "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 several such cubes.
The pieces that make up a cube are specified as follows: divide the cube into a grid of miniature cubes, each labeled with a capital letter. Two adjacent (face-sharing) minicubes are joined together if and only if they carry the same letter. For example, the cube in the first test case consists of solid pieces.
Input
Your program is given the specification of up to different cubes. The first two lines of each specification are the size of the cube, , and a blank line. The remaining lines describe the horizontal layers of the cube from bottom to top. Each layer specification is an square giving the label of every minicube on that layer, followed by a blank line. There are no spaces in the input. The input is terminated by the number on a line by itself.
Output
For each cube, in the order given, print Yes if the cube is stable and No if it is not.