Crosswords

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 Format

The first line of the input will contain the integers R and C (1 ≤ R,C ≤ 21), denoting the row and columns in the crossword grid. The next R rows will have a width of C 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 N (1 ≤ N ≤ 200). The next N 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 Format

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

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Dec 24, 2011
Author: Alex

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

Comments (Search)