Cubic Rube
Time limit1sMemory limit128 MB
Given two connected 5x5 height maps of unit cubes, decide whether the pieces can be rotated and translated in 3D to assemble a full 5x5x5 cube.
- Level
Hard9 of 10
- Topics
- Implementation, Geometry, Brute force, Sorting
- Solved
- No attempts yet
Problem
You work in a Rubik's Cube factory and are designing a new variation: a Rubik's Cube. Your only working prototype fell to the floor and broke into exactly two pieces. You are holding one piece and must decide whether a second piece can complete it.
Each piece is a solid made of unit cubes. Given the two pieces, determine whether they can be fitted together — using rotations and translations in 3D space — to form a solid cube with no gaps and no overlaps.
Input
The first line contains an integer , the number of data sets.
Each data set is given on the next 5 lines. Each line contains two 5-character strings separated by a single space; the left string describes the first solid and the right string describes the second solid. Together the 5 lines give a top-down (bird's-eye) view of each solid as a grid of digits 0–9.
Each digit is the height of that solid at that grid point (the number of unit cubes stacked there). A height of 0 means no cube is present at that point. This is a topographic map: assume there are no hidden gaps underneath any visible part, so a column of height is a solid stack of unit cubes.
Each solid is a single connected piece, and joining the two solids may require translations, not only rotations.
Output
For each data set, print Yes on its own line if the two solids can be fitted together to form a solid cube, or No otherwise.