链接:
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): 427Accepted Submission(s): 76
Problem Description
Did you heard of a little game named "Word Puzzle" ? If you didn't, what a pity !
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.
Input
There is only one test case.
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.
Output
For each word, output the "ROW COL"(quotes for clarity) pair, where ROW is the 0-based row in which the first letter of the word is found, and COL is the 0-based column in which the first letter of the word is found. If the same word can be found more than
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.
Sample Input
3 5
HENRY
GAVIN
MAGIC
HENRY
HGM
HAG
MAVIN
-1
Sample Output
Author
XrtGavin@TJU
Source
题目大意:
给一个字母矩阵, 矩阵里可以按照横着,竖着,斜着(左上--->右下方向), 组成单词。
然后询问一些单词,是否存在矩阵中。如果存在,输出它的起点位置(开始位置在越上面,越左边越好)。
分析与总结:
做这题想了足足有两天啊,我容易吗我.
1. 初看, 觉得水题一枚, 直接枚举矩阵的起点,然后把矩阵中所有可能的单词都进行建Trie树, 在Trie中要保存起点。然后很开心的提交了,结果Memory
Limit Exceeded
2. 然后就一直想啊想啊想.....无线纠结中
3. 终于,我头脑上面的灯泡亮了一下,发现询问的单词只有1W个,那么我们其实就可以把询问单词建成一个Trie树, 然后再枚举矩阵里面的单词,看枚举的单词是否在Trie中,在的话就把位置保存下来。
全部枚举完之后, 在输出在Trie中的询问单词所保存的位置信息。
4. 之后再看看ACM官方标志图片上的那个闪亮的灯泡, 似乎有所感悟...做ACM追求的不就是灯泡亮的那一刻吗?
如果做ACM题, 灯泡都不亮一下就做出来了,乐趣就少了很多。
代码:
#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;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码