Boggle® is a classic word game played on a 4 by 4 grid of letters. The letter grid is randomly generated by shaking 16 cubes labeled with a distribution of letters similar to that found in English words. Players try to find words hidden within the grid.
Words are formed from letters that adjoin horizontally, vertically, or diagonally. However, no letter may be used more than once within a single word.
An example Boggle® letter grid, showing the formation of the words "taxes" and "rise".
The score awarded for a word depends on its length, with longer words being worth more points. Exact point values are shown in the table below. A word is only ever scored once, even if it appears multiple times in the grid.
| No. of letters: |
3 |
4 |
5 |
6 |
7 |
8 or more |
| Points: |
1 |
1 |
2 |
3 |
5 |
11 |
In this problem, your task is to write a program that plays Boggle®. Given a letter grid and a dictionary of words, you are to calculate the total score of all the words in the dictionary that can be found in the grid.
The first line of the input file contains a number N, the number of Boggle® games that follow.
Each Boggle® game begins with 16 capital letters arranged in a 4 by 4 grid, representing the board configuration for that game. A blank line always precedes the letter grid. Following the letter grid is a single number M (1 ≤ M ≤ 100), the number of words in your dictionary for that game. The next M lines contain the dictionary words, one per line, in no particular order. Each word consists of between 3 and 16 capital letters. No single word will appear in the dictionary more than once for a given Boggle® game.
For each Boggle® game in the input, your program should output the total score for that game. Follow the format given in the sample output.
2 TNXO AAEI IOSR BFRH 8 TAXES RISE ANNEX BOAT OATS FROSH HAT TRASH FNEI OBCN EERI VSIR 1 BEER
Score for Boggle game #1: 6 Score for Boggle game #2: 1