poj-1204-Word Puzzles
题目大意：在一个矩阵puzzle中寻找字典中的单词，输出单词的起始位置和方向；使用trie树，叶子节点中记录方向和起始坐标，通过对每个puzzle中的字母为起始位置进行bfs即可。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;int dx[]={-1,-1,0,1,1,1,0,-1};int dy[]={0,1,1,1,0,-1,-1,-1};char puzzle;struct node{ bool f; int next; int d; int x;int y; void Init(){f=0;memset(next,-1,sizeof(next));d=9;x=-1;y=-1;};}a;int p=0;void makeroot(){ a.Init();}void insert(char* str){ int i=0; int cur=0; int index=0; int len=strlen(str); //cout<<"Insert"<<str<<endl; for(i=0;i<len;i++) { cur=str-'A'; if(a.next==-1) { a[++p].Init(); a.next=p; } //cout<<"index now : "<<index<<' '<<cur<<endl; index=a.next; } //cout<<index<<"!!!!!!!!!!"<<endl; a.f=1;}int line,column;bool in(int x,int y){ if(0<=x&&x<line&&y>=0&&y<column) return 1; else return 0;}void find(int x,int y,int d){ int index=0; int cur; int ox; int oy; ox=x; oy=y; while(in(x,y)) { cur=puzzle-'A'; //cout<<"&&&&&&&"<<x<<' '<<y<<' '<<index<<' '<<char(cur+'A')<<' '<<'%'<<a.f<<endl; if(a.f==1) { //cout<<"Find one!"<<endl; a.d=d; a.x=ox; a.y=oy; } if(a.next==-1) { return ; } index=a.next; x+=dx; y+=dy; } if(a.f==1) { //cout<<"Find one!"<<endl; a.d=d; a.x=ox; a.y=oy; }}int ans(char* str){ int index=0; int cur; int len=strlen(str); for(int i=0;i<len;i++) { cur=str-'A'; index=a.next; } //cout<<index<<"$$$$$$$$$$"<<endl; return index;}char ind;int main(){ int i=0; int j=0; int word; makeroot(); cin>>line>>column>>word; for(i=0;i<line;i++) { scanf("%s",puzzle); } //cout<<"puzzle"<<endl; for(i=0;i<word;i++) { scanf("%s",ind); //cout<<'&'<<ind<<endl; insert(ind); } //cout<<"step 2"<<endl; for(i=0;i<line;i++) { for(j=0;j<column;j++) { for(int k=0;k<8;k++) { find(i,j,k); } } } //find(0,15,6); //cout<<"step 3"<<endl; for(i=0;i<word;i++) { int key=ans(ind); printf("%d %d %c\n",a.x,a.y,a.d+'A'); //cout<<a.x<<' '<<a.y<<' '<<char(a.d+'A')<<endl; } return 0;}
页:
[1]