1997 Woburn Computer Programming Challenge
5. Encoding Grid
A kind of grid is cometimes used for encoding messages. Our naval fleet (!) officials decide to use this method of encoding messages for communication with their ship captains. The encoding grid is a square sheet of paper divided into 2Nx2N little squares. N2 of these little squares are cut out (see figure 1).
Let us briefly describe the encoding process. Take a message of length 4N2
characters. Then put an encoding grid onto a blank sheet of paper and beigin
to write the first N2 letters of the message into the cut-out squares
(one letter per square, write letters in the first line from left to right,
then in the second line, etc). See figures 2 for the first step in the message
"HELLOYELLOWWORLD." After finishing the first step rotate the encoding
grid 90 degrees clockwise and continue similarly writing letters. (Figures 3,
After two more steps all of the letters should be written in (figure 5)
we write in the first 4 letters
we rotate and write the next 4
after we remove the grid
after we write in the rest
It is necessary to have a correctly constructed grid, so that we never get a collision (i.e. we see some alread-written letters through holes in the grid after we rotate). We need to always see N2 blank squares after we rotate the grid.
The naval fleet officials encoded thousands of messages with their grid and then they wanted to send them to ships. Unfortunately they lost the grid. Fortunately the naval admiral remembered the original text of one of the messages.
Your task is, given this original message text and the filled-in piece of paper with this encoded message, to find one possible correctly constructed grid with which the message text could have been encoded.
The first line of input contains an integer M specifying the number of
The first line of each test case is N (the encoded message is written on a 2Nx2N grid).
N will be an integer between 1 and 10 inclusive.
The second line of each test case the message which was encoded: a string
of 4N2 characters.
Each of the next 2N lines contains a string of 2N characters representing the letters in the encoded grid. This grid will contain only letters from "A" to "Z".
OutputThe output file should contain one correctly constructed grid for each test case which could have been used to encode the given message into to given grid. The grid should appear in the orientation in which the first N2 letters are written. As in figure 1 above, represent uncut parts of the paper with "#" and holes with "O" (the capital letter, not the number). Leave a blank space between the output for each test case; you may leave a trailing blank line at the end of your output file.
2 2 HELLOYELLOWWORLD HOOY LREO LWEL LLDW 1 SUNK SU KN
O### ##O# O##O #### O# ##
Point Value: 20
Time Limit: 10.00s
Memory Limit: 16M
Added: Sep 28, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3