Problem F

PLAYING BOGGLE

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.

Input

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.

Output

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.

Sample Input

2

TNXO
AAEI
IOSR
BFRH
8
TAXES
RISE
ANNEX
BOAT
OATS
FROSH
HAT
TRASH

FNEI
OBCN
EERI
VSIR
1
BEER

Output for the Sample Input

Score for Boggle game #1: 6
Score for Boggle game #2: 1

---

Sonny Chan
Calgary Collegiate Programming Contest 2006


搜索在 4*4 的方格中是否有匹配的字串，得分按照字串的長度。

跟 google 搜索出來的，讓我在較勁一下誰也得比較好。


#include <stdio.h>
#include <string.h>
char g[10][10], s[30];
char used[10][10] = {};
int found;
void dfs(int x, int y, int idx) {
    if(found)   return;
    if(s[idx] == '\0')  found = 1;
    if(x < 0 || y < 0 || x >= 4 || y >= 4)
        return;
    if(g[x][y] != s[idx] || used[x][y])
        return;
    used[x][y] = 1;
    dfs(x+1, y+1, idx+1);
    dfs(x+1, y, idx+1);
    dfs(x+1, y-1, idx+1);
    dfs(x, y+1, idx+1);
    dfs(x, y-1, idx+1);
    dfs(x-1, y+1, idx+1);
    dfs(x-1, y, idx+1);
    dfs(x-1, y-1, idx+1);
    used[x][y] = 0;
}
int main() {
    int testcase, cases = 0;
    int i, j, n;
    scanf("%d", &testcase);
    while(testcase--) {
        for(i = 0; i < 4; i++)
            scanf("%s", g[i]);
        scanf("%d", &n);
        int ret = 0;
        while(n--) {
            scanf("%s", s);
            found = 0;
            for(i = 0; i < 4; i++)
                for(j = 0; j < 4; j++)
                    dfs(i, j, 0);
            int len = strlen(s);
            if(found) {
                if(len == 3 || len == 4)
                    ret++;
                else if(len == 5)
                    ret += 2;
                else if(len == 6)
                    ret += 3;
                else if(len == 7)
                    ret += 5;
                else if(len >= 8)
                    ret += 11;
            }
        }
        printf("Score for Boggle game #%d: %d\n", ++cases, ret);
    }
    return 0;
}