The Problem

Given an input dictionary read in from a file to use for all test cases, and several word search grids, identify all words from the dictionary that appear in each word search grid.

The Input

(of word search grids, to be read in from standard input) The first line of the input file will contain a single positive integer, c (c ≤ 100), representing the number of input cases. The input cases follow, one per line. The first line of each input case will contain two positive integers, r (4 ≤ r ≤ 300), and c (4 ≤ c ≤ 300), representing the number of rows and columns, respectively, in the word search grid. The following r lines will contain strings of exactly c characters, all of which will be lowercase letters for each row of the word search grid for that input case.

The Output

For each case, output a header with the following format:

Words Found Grid #k:

where k is the grid number starting with 1. (Please pay attention to the capitalization above, the pound sign and the colon. You will lose a small amount of credit if you don't use this exact format.)

Output all the words from the dictionary found in the grid on the following lines, one per line. You may output these in any order and you may output the same word more than once, but you should not output any string that isn't in the dictionary, or output any valid word that does not appear anywhere in the grid. I will assign a small amount of extra credit if you can only output each valid word once and another little bit of extra credit if you output these words in alphabetical order. You can only get the extra credit if your solution is 100% correct.

Sample Input                                                                                                    Sample Output

2                                                                                                                              Words Found Grid #1:

4 4                                                                                                                          trap

Syrt                                                                                                                       part

gtrp                                                                                                                        cats

faaq                                                                                                                       Words Found Grid #2:

pmrc                                                                                                                      swing    

5 6                                                                                                                          wing  

swingh                                                                                                                  letter    

abcdef

rettel

ayzgfd

cmtydh

Specification Details You must use dynamic memory allocation to store the input dictionary and each individual word search grid. You must free your memory appropriately. You must read the input dictionary from the file dictionary.txt, which will be posted online.   

Deliverables Please turn in a single source file, wordsearch.c, with your solution to this problem via Webcourses before the due date/time for the assignment. Make sure that your program reads the puzzles from standard in and outputs all information to standard out, as previously shown in lab. Note that the dictionary will be read in from a file.