When Bob learned that he was to be sent abroad to work on an oil rig,
he resolved that he would write regularly to his girlfriend.
"We'll have to encrypt our correspondence," he told Alice, "so that my
tender feelings remain unknown to the rest of the crew."
Alice showed Bob a simple kind of text encryption that makes use of
a square cardboard grille divided into equal-sized cells, exactly one
quarter of which are punched out to make holes. For example, a six-by-six
grille might be configured as follows, where '.' stands for a hole and
'X' for a cell that has been left intact.
XXXXXX
.XXXX.
X.XX..
XXX.XX
X.XXXX
XX.XX.
To encrypt a message, Bob begins writing plaintext into the grille, one
character per hole, proceeding from left to right within each row and
running through the rows from top to bottom. Once all holes are filled,
he rotates the grille ninety degrees clockwise, and continues the message
where he left off. After two more quarter turns, he has written a full
square of coded text, and must begin a new one. Upon receipt of the
message, Alice uses an identical grille to decrypt each square. If, for
example, Bob's plaintext were "supercalifragilisticexpialadociously",
Alice would receive the following code.
idocfc
sriaeu
gpxoer
piicau
laslla
iylsti
Not just any grille will do for this purpose, as Bob discovered when
he tried to make one by cutting out holes at random. He found that
this haphazard grille wouldn't let him write out a full square of
text in the prescribed manner. After fewer than four quarter-turns,
some holes revealed previously written characters. Alice assured him
that this was a grave flaw. An encoding grille must permit one to fill
the entire square by making three quarter-turns, and it must show each
cell of the square exactly once. Bob, alas, had a lyrical soul and not
a mathematical one. He could not perceive the properties that make a
grille suitable for use with this encryption technique. Can you?
You are given a String[] describing a grille row by row, in
the style shown above, with no more than a quarter of its holes punched
out. If it is not possible to make a complete and valid encoding grille
from this configuration by punching out zero or more additional holes,
then return an empty String[]. Otherwise, punch out the
necessary holes in the upper-left quadrant to make a complete and valid
grille, and return it in the same format as the input.
|