/*
LANG: C
TASK: boggle
*/
#include <stdio.h>

#define usedbit(i,j)  (1<<((i-1)*5+(j-1)))
char word[100];

char bog[7][9];	/* boggle matrix is surrounded by row/column of zeroes */
struct list_f {
    int starti;
    int startj;
    struct list_f *list_next;
};
struct list_f *startlist[26];
FILE *fout;
main() {
    FILE *fin = fopen("boggle.in", "r");
    int letterindex, i, j;
    struct list_f *l;
    char c, *p;
    fout = fopen("boggle.out", "w");
    system ("ls -l");
    for (i = 1; i <= 5; i++) {
    	fgets (&bog[i][1], 7, fin);
	bog[i][6] = '\0';
    }
    fclose (fin);
    for (i = 1; i <= 5; i++) {
	for (j = 1; j <= 5; j++) {
	    letterindex = bog[i][j]-'A';
	    l = (struct list_f *)malloc(sizeof(struct list_f));
	    l->starti = i;
	    l->startj = j;
	    l->list_next = startlist[letterindex];
	    startlist[letterindex] = l;
	}
    }
    fin = fopen("dict6.txt", "r");
    while (fgets (word, 100, fin)) {
	for (p = word; *p != '\n'; p++) 
	    if (startlist[*p-'A'] == 0)
		goto LOOPEND;
	*p = '\0';
	for (l = startlist[word[0]-'A']; l; l=l->list_next) {
	    i = l->starti;
	    j = l->startj;
	    lookword(&word[1], i, j, usedbit(i,j));
	}
LOOPEND:;
    }
    exit (0);
}
/*
words no longer than 80 characters
*/

lookword (p, i, j, usedbits)
char *p;		/* character within word we're seeking */
{
    int di, dj;
    if (*p == '\0') {	/* winner? */
	fprintf(fout, "%s\n", word);
	return;
    }
    for (di = -1; di <= 1; di++) {
	for (dj = -1; dj <= 1; dj++) {
	    if (di == 0 && dj==0) continue;
	    if (bog[i+di][j+dj] == 0) continue;
	    if (usedbits & usedbit(i+di, j+dj)) continue;
	    if (bog[i+di][j+dj] == *p) 
		lookword(p+1, i+di, j+dj, usedbits | usedbit(i+di, j+dj));
	}
    }
}