Boggle Blitz

In the game of Boggle, you are presented with an NXN table of letters. The object is to find words in the mix of letters. A word may be started anywhere in the table and is constructed by forming a chain of adjacent letters. Adjacent means diagonal, vertical or horizontal. A word cannot use any character from the table more than once.

Here is an example of a 4X4 table: bile 
tglp 
aest 
here

The following is a partial list of legal words that can be found using the above rules:

bill
gates
slept
here

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

In “Boggle Blitz” you will be given an integer number, N, on a single line. N is the number of characters on each side of the table, giving a total of characters. N can range from 1 to 20. N lines of N characters each will follow giving you the arrangement of the table.

Your task is to find all the legal words in the table. Be sure that your program is efficient!

In case you forgot to bring a dictionary, you are in luck because we are not using English words. Instead, we have redefined “word” to mean an increasing (by ASCII value) chain of characters from length 3 to length  . “ABCDE” is a legal five letter word. “MICROSOFT” is not legal because the sequence is not increasing. “BILL” is also illegal because L is not greater than L. “BIL”, however, is legal.

Sample Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

Your program should output the list of unique words sorted according to the following criteria:

1. Shorter words are before longer words
2. Words are sorted lexigraphically by ASCII value

Add no blank lines or spaces. If no legal words can be found, print nothing.

Sample Input

2

3
one
top
dog

4
abcd
bcda
cdab
dabc

Sample Output

dop
dot
eno
enp
ent
eop
eot
gop
got
nop
not
enop
enot

abc
abd
acd
bcd
abcd

C Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define MAXN 500000

char F[22][22];
char Temp[22];
char Word[MAXN][30];
char Bog[20][21];
int K, N, L,MAX;

int com(const void *a, const void *s) {
   char *d = (char *)a;
   char *e = (char *)s;
   int m = strlen(d);
   int n = strlen(e);
   if(m != n) return m-n;
   return strcmp((char*)a, (char *)s);
}

void Gen(int r, int c, int level)  {

	int k;
	if(level) {
	      if(Temp[level-1]>=Bog[r][c]) return;
	}
	Temp[level] = Bog[r][c];
	if(level >= 2) {
	     for(k = 0; k<=level; k++)
		Word[K][k] = Temp[k];
		Word[K][k] = NULL;
		K++;
	}
	if(level == N*N - 1)     return;


	for(int i = -1; i<=1; i++) {
	   for(int j = -1; j<=1; j++) {
	       if(i ==0 && j==0) continue;
	       int nr = r+i;
	       int nc = c+j;
	       if(nr <0 || nr>= N ||nc<0 || nc>=N|| F[nr][nc] == 1) continue;
	       F[nr][nc] = 1;
	       Gen(nr,nc,level+1);
	       F[nr][nc] = 0;
	   }
	}
}


void Cal() {
    int i, j;
    K = 0;
    for( i = 0; i<N; i++)
       for(j = 0; j<N; j++) {
	  F[i][j] = 1;
	  Gen(i,j,0);
	  F[i][j] = 0;
       }
}

void sort() {
   int i;
   if(K ==0) return;
   qsort(Word,K,sizeof(Word[0]),com);
   printf("%s\n",Word[0]);
   for(i = 1; i<K; i++) {
     if(!strcmp(Word[i],Word[i-1])) continue;
     printf("%s\n",Word[i]);
  }
}

void main() {
    int i,kase;
	char input[10];
	gets(input);
   sscanf(input,"%d",&kase);
   gets(input);
   while(kase--) {
       gets(input); 
	   sscanf(input,"%d",&N);

	  for(i = 0; i<N; i++)
	    gets(Bog[i]);
	  Cal();
	  sort();
       
	  if(kase) {putchar('\n');gets(input);}
   }
}