思路: 将所有输入的单词插入trie 树中,再在table 中枚举每个点的八个方向,作为单
词的起点。如果枚举成功。这标记出现的单词。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) code 1 #include<iostream> 2 using namespace std; 3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) const int dir[8][2]= { {-1,0}, {-1,1}, {0,1}, {1,1}, {1,0}, {1,-1}, {0,-1}, {-1,-1}}; 5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 6 typedef struct Tnode 7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 8 int end; 9 Tnode * next[26]; 10 Tnode() 11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 12 end=-1; 13 memset(next,0,sizeof(next)); 14 } 15 }Trie; 16![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 17 Trie *root=new Trie; 18 char map[1010][1010]; 19 int res[1010][3]; 20 int l,c,w,px,py; 21![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 22 void Insert(Trie *cur,char *s,int id) 23![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 24 int i; 25 if(*s==0) 26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 35 void input() 36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 37 int i; 38 char word[1010]; 39![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 40 scanf("%d%d%d",&l,&c,&w); 41![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif) 42 for(i=0;i<l;i++) 43 scanf("%s",map[i]); 44 for(i=0;i<w;i++) 45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 46 scanf("%s",word); 47 Insert(root,word,i); 48 } 49 } 50![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 51 void search(Trie *cur,int x,int y,int k) 52![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 53 if(cur==NULL) 54 return ; 55 if(cur->end>-1) 56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 67 int solve() 68![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 74 px=i;py=j; 75 search(root,i,j,k); 76 } 77 return 1; 78 } 79![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 80 void output() 81![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 87 int main() 88![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 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 |
|
公告
常用链接
留言簿
随笔分类
随笔档案
文章分类
文章档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|