Woburn Challenge 1999 - Suicidal

Message in a Bottle

James Bond is stuck at sea after his black power raft was destroyed. So far, no one has found him (they just figured he was "indisposed") and so he has become desperate. He decides to send a message in a bottle in the hopes that M finds it. But this is after all MI6 and so everything has to be done secretively. He writes his message in invisible ink on a square piece of paper and then cuts the paper into different shapes (at most 10 shapes). He then stuffs these shapes into a bottle and sends it on its way to London. As per protocol, the shapes all have edges parallel to the edges of the paper. The paper is a standard MI6-issued 10x9 (height x width) piece of paper. Some time later…

Back in London, M retrieves the bottle and attempts to put the paper back together in order to retrieve the message. But there's a good reason she's not an active agent because she needs help putting the paper back together. You are given the shapes and you must put it back together into the original square. The shapes will be masked by a character to indicate its shape

For example,

 1111
 11

would denote an L-shaped piece. You must output the completed square. Note that the pieces are indicated with a character designation (i.e. this piece has been designated "1") to ensure that in the completed square, the exact positions of all the pieces placed are evident. In the event of more than one correct completion, output any of them.

Input

Line 1: Number of input sets.
The next few lines will contain the input sets, which are represented as follows:
- 1st line: a positive integer N≤10, the number of pieces
- Next few lines will contain character-masks of the pieces.
- Each piece will be separated by a line containing a single 0 (a 0 will never be used to bit-mask a shape)

Output

Output the original letter as it must have appeared (if more than one exists, print out any one possibility).

Sample Input

1
6
11111
1
111
0
    222
22222
  22222
0
        3
      333
        3
333333333
333  3333
0
   44
444444444
444444444
0
555555
5555
5
0
     666
   66666
66666666
0

Sample Output

111112223
122222333
111222223
333333333
333443333
444444444
444444444
555555666
555566666
566666666

All Submissions
Best Solutions

Point Value: 25
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...