Paper Cutting
Time limit2sMemory limit128 MB
Decide whether five fixed-shape pieces can be translated without rotation to exactly tile an L x L grid, then print the lexicographically smallest piece-number layout or gg if impossible.
- Level
Medium7 of 10
- Topics
- Backtracking, Bit manipulation, Brute force, Implementation
- Solved
- No attempts yet
Problem
Song Yujin has an L x L square sheet of grid paper. The sheet has L cells across and L cells down, and each cell is a 1 x 1 square.
Cha Younghoon cut the sheet along grid lines into exactly 5 pieces. Yujin must now place the five given pieces back into an L x L square without rotating any piece.
Input
The first line contains the side length L of the square. (3 <= L <= 10)
Then the descriptions of the first through fifth pieces are given in order.
Each piece is described in the following format.
- The first line contains the piece height N and width M. (1 <= N, M <= L)
- The next N lines describe the shape of the piece. Each line has length M and consists only of
#and.. #means a cell occupied by the piece, and.means an empty cell.- In the given bounding rectangle, the first row, last row, first column, and last column each contain at least one
#.
Output
If the five pieces can be placed without rotation inside the L x L square so that they do not overlap and every cell is filled, print the piece number occupying each cell. Pieces are numbered 1 through 5 in input order.
Print L lines, each containing the L numbers in that row.
If there are multiple valid arrangements, concatenate all rows from top to bottom and print the arrangement whose resulting string is lexicographically smallest.
If no valid arrangement exists, print gg.