思路: 将所有输入的单词插入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}
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
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 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|