思路：
将所有输入的单词插入trie 树中，再在table 中枚举每个点的八个方向，作为单
词的起点。如果枚举成功。这标记出现的单词。
  code
1 #include<iostream>
2using namespace std;
3
4const int dir[8][2]= {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
5
6typedef struct Tnode
7{
8 int end;
9 Tnode * next[26];
10 Tnode()
11  {
12 end=-1;
13 memset(next,0,sizeof(next));
14 }
15 }Trie;
16
17Trie *root=new Trie;
18char map[1010][1010];
19int res[1010][3];
20int l,c,w,px,py;
21
22void Insert(Trie *cur,char *s,int id)
23{
24 int i;
25 if(*s==0)
26 { cur->end=id;
27 return ;
28 }
29 i=*s-'A';
30 if(cur->next[i]==NULL)
31 cur->next[i]=new Trie;
32 Insert(cur->next[i],s+1,id);
33}
34
35void input()
36{
37 int i;
38 char word[1010];
39
40 scanf("%d%d%d",&l,&c,&w);
41
42 for(i=0;i<l;i++)
43 scanf("%s",map[i]);
44 for(i=0;i<w;i++)
45 {
46 scanf("%s",word);
47 Insert(root,word,i);
48 }
49}
50
51void search(Trie *cur,int x,int y,int k)
52{
53 if(cur==NULL)
54 return ;
55 if(cur->end>-1)
56 {
57 res[cur->end][0]=px;
58 res[cur->end][1]=py;
59 res[cur->end][2]=k;
60 }
61 if(x<0||x>=l||y<0||y>=c)
62 return ;
63 int i=map[x][y]-'A';
64 search(cur->next[i],x+dir[k][0],y+dir[k][1],k);
65}
66
67int solve()
68{
69 int i,j,k;
70 for(i=0;i<l;i++)
71 for(j=0;j<c;j++)
72 for(k=0;k<8;k++)
73 {
74 px=i;py=j;
75 search(root,i,j,k);
76 }
77 return 1;
78}
79
80void output()
81{
82 int i;
83 for(i=0;i<w;i++)
84 printf("%d %d %c\n",res[i][0],res[i][1],res[i][2]+'A');
85}
86
87int main()
88{
89 input();
90 solve();
91 output();
92 return 0;
93}
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 25 | 26 | 27 | 28 | 29 | 30 | 31 | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | 8 | 9 | 10 | 11 | 12 | 13 | 14 | | 15 | 16 | 17 | 18 | 19 | 20 | 21 | | 22 | 23 | 24 | 25 | 26 | 27 | 28 | | 29 | 30 | 31 | 1 | 2 | 3 | 4 |
|
公告
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|