Folding a Cube
Time limit1sMemory limit512 MB
Given a connected arrangement of six unit squares with no 2x2 block, decide whether it can be folded into a cube.
- Level
Medium7 of 10
- Topics
- DFS, Geometry, Implementation, Backtracking
- Solved
- No attempts yet
Problem
It is well known that six unit squares attached together in a "cross" shape can be folded into a cube.
But what about other shapes? That is, given six unit squares attached together along some of their sides, can this arrangement be folded to form a unit cube?
Input
The input consists of 6 lines, each containing 6 characters, describing the initial arrangement of unit squares. Each character is either a ., meaning an empty cell, or a #, meaning a unit square.
There are exactly 6 occurrences of #, representing the unit squares. They form a single connected component, meaning it is possible to reach any # from any other # without stepping on a . using only horizontal and vertical moves. Furthermore, there is no 2 × 2 subsquare consisting entirely of #. That is, the following pattern does not appear in the input.
##
##
Output
If the unit squares can be folded into a cube, output can fold. Otherwise, output cannot fold.