You are the average grandson, always anxious to impress your grandmother so that she will bake you tasty treats. Your grandmother is a very intelligent word wizard and happens to enjoy crosswords. She has the ability to look at any hint and produce the answer. The problem is, she is losing her vision, and is constantly having a hard time reading the number labels on the boxes of her crosswords. Being the wonderful grandchild you are, you have decided to write a program that will position words onto a crossword grid, after your grandma has solved them.
Input Specification
The first line of the input will contain the integers and
, denoting the row and columns in the crossword grid.
The next rows will have a width of columns, containing the grid
of the unsolved crossword. A #
represents a void space (i.e. a space
where no letters may be placed) and a .
represents an empty space,
where a letter should be placed. The following line will contain the
integer . The next lines will contain the
words, in no particular order, that must be placed either horizontally
OR vertically on the grid.
Like a normal crossword, words are only valid when read left-right or up-down. Words must start and end either on the edge of the grid or before/after a void space. Each word will only contain the uppercase letters A through Z. You may assume that there will only be one possible solution for every test case, and that all words will be at least 2 letters long.
Output Specification
The output should contain the solved crossword.
Sample Input 1
1 15
##.........####
1
CROSSWORD
Sample Output 1
##CROSSWORD####
Sample Input 2
3 6
#.....
....##
###...
6
AT
ME
DOG
GOD
VETO
MAGIC
Sample Output 2
#MAGIC
VETO##
###DOG
Comments