trie.txt

acm 常用算法和代码库

#include<iostream>
using namespace std;
char dic[1002][1002];
char word[1002];
int l,c,w,index;
int x,y,dri;
int my[]= {0,1,1,1,0,-1,-1,-1};
int mx[]= {-1,-1,0,1,1,1,0,-1};
typedef struct trietree
{
	struct trietree* next[26];
	int isword;
}
node;
struct ANS
{
	int x,y;
	char d;
}
ans[1002];
node root;
void insert(char *tar)
{
	node *p=&root;
	int id,i;
	while (*tar)
	{
		id=*tar-'A';
		if(p->next[id]==NULL)
		{
			p->next[id]=new node;
			p->next[id]->isword=0;
			for(i=0;i<26;++i)p->next[id]->next[i]=NULL;
		}
		p = p->next[id];
		tar++;
	}
	p->isword=index;
}
void search(int tx,int ty,int td)
{
	node *p = &root;
	int id;
	while (tx>=0&&tx<l&&ty>=0&&ty<c)
	{
		id=dic[tx][ty]-'A';
		if(p->next[id]==NULL)return;
		p = p->next[id];
		if(p->isword&&ans[p->isword].d==0)
		{
			ans[p->isword].x=x;
			ans[p->isword].y=y;
			ans[p->isword].d=dri+'A';
		}
		tx+=mx[td];
		ty+=my[td];
	}
}
int main()
{
	int i;
	scanf("%d%d%d",&l,&c,&w);
	index = 1;
	for (i=0;i<l;i++)scanf("%s",dic[i]);
	for (i=0;i<w;i++)
	{
		scanf("%s",word);
		insert(word);
		index++;
	}
	for(x=0;x<l;++x)
	for(y=0;y <c;++y)
	for(dri=0;dri<8;++dri)
	search(x,y,dri);
	for(i=1;i<=w;++i)
	printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].d);
	return 0;
}