http://blog.csdn.net/shuangde800/article/details/8112433
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1857
题目：
Word Puzzle
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 427 Accepted Submission(s): 76
In the game, you will be given a rectangular grid of letters, in which several words are hidden. Each word may begin anywhere in the puzzle, and may be oriented in any straight line horizontally, vertically, or diagonally. However, the words must all go down,
right, or down-right. A dictionary is also given to you, indicating the words to be found in the grid.
You task is to find the locations of each word within the grid.
The first line is two integers R and C separated by a whitespace. R (20 ≤ R ≤ 500) is the number of rows of the grid. C (20 ≤ C ≤ 500) is the number of columns of the grid.
The following R lines, each line will contains exactly C characters without anything else. Each character is in the range 'A' - 'Z'.
A blank line will be followed after the grid.
The following lines, each line contains a unique word in the dictionary. Each word will contain between 1 and 20 characters ( also in the range 'A' - 'Z'). The dictionary consists of at most 10000 words.
-1 means the end of dictionary.
once, the location in the lowest-indexed row should be returned. If there is still a tie, return the location with the lowest-indexed column. If a word cannot be found in the grid, return "-1 -1" for the word.
3 5 HENRY GAVIN MAGIC HENRY HGM HAG MAVIN -1
0 0 0 0 0 0 -1 -1
.Limit Exceeded
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int KIND = 26;
const int MAXN = 1000000;
int cnt_node;
int R,C;
char map[505][505];
char word[10005][22];
struct node{
bool isword;
int r,c;
node* next[KIND];
void init(){
r=c=-1;
isword=false;
memset(next, 0, sizeof(next));
}
}Heap[MAXN];
inline node* new_node(){
Heap[cnt_node].init();
return &Heap[cnt_node++];
}
// 把询问的单词建Trie树
void insert(node* root, char *str){
for(char *p=str; *p; ++p){
int ch=*p-'A';
if(root->next[ch]==NULL)
root->next[ch] = new_node();
root=root->next[ch];
}
root->isword=true;
}
// 对矩阵中枚举的单词查找是否再Trie树中
void search(node* root, char *str, int row, int col){
for(char *p=str; *p; ++p){
int ch=*p-'A';
if(root->next[ch]==NULL)
return ;
root=root->next[ch];
if(root->isword && root->r==-1 && root->c==-1){
root->r=row, root->c=col;
}
}
if(root->isword && root->r==-1 && root->c==-1){
root->r=row, root->c=col;
}
}
// 输出询问的单词在矩阵中的位置
void output(node* root, char *str){
for(char *p=str; *p; ++p){
int ch=*p-'A';
if(root->next[ch]==NULL)
return;
root=root->next[ch];
}
if(root->isword)
printf("%d %d\n", root->r, root->c);
}
int main(){
// Trie init
cnt_node=0;
node* root=new_node();
scanf("%d%d%*c",&R,&C);
for(int i=0; i<R; ++i){
gets(map[i]);
}
gets(word[0]); //消除空格
int pos=0;
while(gets(word[pos])){
if(word[pos][0]=='-') break;
insert(root, word[pos++]);
}
char str[30];
for(int i=0; i<R; ++i){
for(int j=0; j<C; ++j){
int end_r,end_c=j;
// 竖下
if(i+20<R)
end_r=i+20;
else
end_r=R;
memset(str, 0, sizeof(str));
for(int k=i,p=0; k<end_r; ++k)
str[p++]=map[k][j];
search(root, str, i, j);
// 横着
if(j+20<C)
end_c=j+20;
else
end_c=C;
memset(str, 0, sizeof(str));
for(int k=j,p=0; k<end_c; ++k)
str[p++]=map[i][k];
search(root, str, i, j);
// 斜着
int r=i, c=j,p=0;
memset(str, 0, sizeof(str));
while(r<end_r && c<end_c){
str[p++]=map[r][c];
++r, ++c;
}
search(root,str,i,j);
}
}
for(int i=0; i<pos; ++i){
output(root, word[i]);
}
return 0;
}