Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Another Puzzling Problem
Time Limit: 1000MSMemory Limit: 10000K
Total Submissions: 341Accepted: 115

Description

You are to write a program to solve jigsaw puzzles. The input will contain the dimension of the puzzle, the dimension of the pieces, and the actual pieces of the puzzle. The pieces will be made up of ASCII characters. You are to create an output which consists of the solved puzzle.

Input

The first line of the input will contain three integers. These are the dimension of the puzzle (puzzles are always square), and the height and width of the pieces, respectively. The dimension of the puzzle can range from 2 to 10, and the height and width of each puzzle piece can range from 1 to 25. For example, the input "2 2 3" (without the quotes, of course) specifies a puzzle that is 2 * 2 pieces in size, with individual pieces that are 2 * 3 characters in size. All pieces have the same height and width.

The rest of the specifies the puzzle pieces in arbitrary order. Each piece is specified by an image of the piece followed by a line containing four integers ranging from -5 to +5. These values indicate the shape of the top, left, bottom and right edges of the puzzle piece, respectively. Values of 0 identify straight (i.e. outer) edges. Positive and negative edges of the same value are pairs that interlock (e.g. -5 interlocks with +5, -4 with +4, etc.). Puzzle pieces may not be rotated, and all pieces will be unique (that is, no two pieces will have the same values for all four edges). A blank line separates each puzzle piece.

Note that spaces (ASCII character 32) are valid characters in a puzzle piece. If they appear at the end of a line (or are the only characters on a line), then they will appear in the input file. All pieces will be a rectangular block of characters (ASCII codes 32 to 127), even if spaces at the end of a line make it appear differently. In short, spaces should be treated no differently than any other character.

Output

The output should simply contain the solved puzzle in the proper arrangement. The input puzzle will have one and only one solution.

Sample Input

2 8 14
88,           
8888.         
:8888b        
  8888        
-.:888b       
' d8888       
 ,88888       
':88888       
0 3 -1 0

         o8%88
       o88%888
      8'-    -
     8'       
    d8.-=. ,==
    >8 `~` :`~
    88        
    88b. `-~  
0 0 -5 -3

.:88888       
:::8888       
:' 8888b      
    8888b     
    ,%888b.   
    %%%8--'-. 
   _%-' ---  -
.-'   =  --.  
1 4 0 0

    888b ~==~ 
    88888o--:'
    `88888| ::
    8888^^'   
   d888       
  d88%        
 /88:.__ ,    
     '''::===.
5 0 0 -4

Sample Output

         o8%8888,           
       o88%8888888.         
      8'-    -:8888b        
     8'         8888        
    d8.-=. ,==-.:888b       
    >8 `~` :`~' d8888       
    88         ,88888       
    88b. `-~  ':88888       
    888b ~==~ .:88888       
    88888o--:':::8888       
    `88888| :::' 8888b      
    8888^^'       8888b     
   d888           ,%888b.   
  d88%            %%%8--'-. 
 /88:.__ ,       _%-' ---  -
     '''::===..-'   =  --.  

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator