[UVA][枚舉] 487 - Boggle Blitz
In the game of Boggle, you are presented with an 
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 
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:
- Shorter words are before longer words
- 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
#include <stdio.h>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;
char board[21][21], used[21][21] = {}, tmp[401];
set<string> ans;
int n;
void dfs(int x, int y, int idx) {
if(idx >= 3) {
tmp[idx] = '\0';
ans.insert(tmp);
}
if(x < 0 || y < 0 || x >= n || y >= n)
return;
if(idx > 0 && board[x][y] <= tmp[idx-1])
return;
if(used[x][y])
return;
tmp[idx] = board[x][y];
used[x][y] = 1;
dfs(x+1, y, idx+1);
dfs(x-1, y, 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+1, idx+1);
dfs(x+1, y+1, idx+1);
dfs(x+1, y-1, idx+1);
used[x][y] = 0;
}
bool cmp(string a, string b) {
return a.length() < b.length();
}
int main() {
int t, i, j;
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
for(i = 0; i < n; i++) {
scanf("%s", board[i]);
}
ans.clear();
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
dfs(i, j, 0);
}
}
string tot[50000];
int totIdx = 0;
for(set<string>::iterator it = ans.begin();
it != ans.end(); it++) {
tot[totIdx++] = *it;
}
stable_sort(tot, tot+totIdx, cmp);
for(i = 0; i < totIdx; i++)
cout << tot[i] << endl;
if(t)
puts("");
}
return 0;
}