题目大意:在一个矩阵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[1050][1050];
struct node
{
bool f;
int next[26];
int d;
int x;int y;
void Init(){f=0;memset(next,-1,sizeof(next));d=9;x=-1;y=-1;};
}a[10000010];
int p=0;
void makeroot()
{
a[p=0].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[i]-'A';
if(a[index].next[cur]==-1)
{
a[++p].Init();
a[index].next[cur]=p;
}
//cout<<"index now : "<<index<<' '<<cur<<endl;
index=a[index].next[cur];
}
//cout<<index<<"!!!!!!!!!!"<<endl;
a[index].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[x][y]-'A';
//cout<<"&&&&&&& "<<x<<' '<<y<<' '<<index<<' '<<char(cur+'A')<<' '<<'%'<<a[index].f<<endl;
if(a[index].f==1)
{
//cout<<"Find one!"<<endl;
a[index].d=d;
a[index].x=ox;
a[index].y=oy;
}
if(a[index].next[cur]==-1)
{
return ;
}
index=a[index].next[cur];
x+=dx[d];
y+=dy[d];
}
if(a[index].f==1)
{
//cout<<"Find one!"<<endl;
a[index].d=d;
a[index].x=ox;
a[index].y=oy;
}
}
int ans(char* str)
{
int index=0;
int cur;
int len=strlen(str);
for(int i=0;i<len;i++)
{
cur=str[i]-'A';
index=a[index].next[cur];
}
//cout<<index<<"$$$$$$$$$$"<<endl;
return index;
}
char ind[1010][1050];
int main()
{
int i=0;
int j=0;
int word;
makeroot();
cin>>line>>column>>word;
for(i=0;i<line;i++)
{
scanf("%s",puzzle[i]);
}
//cout<<"puzzle"<<endl;
for(i=0;i<word;i++)
{
scanf("%s",ind[i]);
//cout<<'&'<<ind[i]<<endl;
insert(ind[i]);
}
//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[i]);
printf("%d %d %c\n",a[key].x,a[key].y,a[key].d+'A');
//cout<<a[key].x<<' '<<a[key].y<<' '<<char(a[key].d+'A')<<endl;
}
return 0;
}
分享到:
相关推荐
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ2002-Squares 解题报告+AC代码
北大POJ1496-Word Index 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3