Problem E
Enigma
The
Imitation Game is a 2014 film based in 1939 during World
War II. It follows the newly created British intelligence
agency MI6 as they employ Cambridge mathematics alumnus Alan
Turing to crack the German Enigma machine. At the time,
cryptographers everywhere believed it to be uncrackable. By the
end of the film, Turing and his team were able to successfully
crack the Enigma, ultimately winning the war for the
allies.
If you have seen the film, you would know that, brilliant as
he is, Alan Turing didn’t crack the code on his own. He
employed help from his group of carefully selected colleagues.
But how exactly did he select them? He placed crosswords
puzzles all over Great Britain in the hopes that other
brilliant minds would be able to solve them to qualify as
candidates for his challenging project.
Those who solved his crosswords were given a special test to
further evaluate their candidacy. Turing’s crosswords were
extremely befuddling, but you are smart enough to figure out
the words from the clues alone. However, you’re not really a
spatial thinker, so you need some help positioning them onto
the grid. Thanks to the help of modern day computing, perhaps
you too can consider yourself worthy to become part of his
famous team.
Given an empty crossword puzzle and a scrambled list of all of the solutions to the clues, your task is to position them appropriately on the grid. Like all typical crosswords, words are only valid when read left-right or up-down. Words must start/end either on the edge of the grid or beside a void space.
Input
The first line of input consists of two space-separated
integers, $R$ and
$C$ ($1 \leq R, C \leq 21$), specifying the
number of rows and columns in the crossword grid.
$R$ line follow, each
of which consists of $C$
characters, specifying the grid for the unsolved crossword.
Within this grid, a “#" character
represents a void space (i.e. a space where no letters may be
placed) and a “." character
represents an empty space, where a letter should be
placed.
The next line consists of a single integer $N$ ($1
\leq N \leq 200$).
$N$ lines follow, each of which consists of a single string of at least length $2$, consisting of only uppercase letters from “A" to “Z". These lines, given in no particular order, specify every word of the crossword solution that must be placed either horizontally or vertically on the grid.
Output
Print an $R$ by
$C$ grid consisting of the
solved crossword.
You may assume that there will be exactly one solution in every
test case.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 15 ##.........#### 1 CROSSWORD |
##CROSSWORD#### |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 6 #..... ....## ###... 6 AT ME DOG GOD VETO MAGIC |
#MAGIC VETO## ###DOG |
