题目分析

给定一个由字母组成的二维地图和一个单词列表，要求在地图中找出所有出现在列表中的单词。单词可以沿着8个方向（水平、垂直、对角线）连续延伸，且搜索到单词的终止节点时仍需继续深入（可能存在更长的单词包含当前单词作为前缀）。

解题思路

1. 构建Trie树：

   • 将所有待搜索的单词插入Trie树中，标记每个单词的终止节点。
   • Trie树的节点结构包含：
     • 子节点指针（对应26个字母）。
     • 标记 is_end，表示当前节点是否为某个单词的结尾。

2. 地图搜索：

   • 遍历地图上的每一个点 $(i, j)$ 作为搜索起点。
   • 从 $(i, j)$ 出发，向8个方向（上、下、左、右、对角线）进行深度优先搜索（DFS）。
   • 搜索过程中：
     • 若当前路径构成的字符串在Trie树中不存在前缀，则剪枝。
     • 若到达某个节点满足 is_end = true，则记录该单词，但不终止搜索（可能存在更长的匹配单词）。

3. 去重与输出：

   • 使用哈希表记录已找到的单词，避免重复。
   • 最终按字典序输出所有唯一匹配的单词。

关键点

• Trie树的终止节点处理：
  • 即使当前路径已构成完整单词，仍需继续搜索（如地图中存在 "app" 和 "apple"，搜索到 "app" 时不应停止）。
• 搜索方向：
  • 8个方向的DFS需注意边界条件，防止数组越界。
• 时间复杂度优化：
  • Trie树剪枝避免无效搜索，最坏情况下时间复杂度为 $O(n \times m \times 8^L)$，其中 $L$ 为最长单词长度。

复杂度分析

• 时间复杂度：
  • 构建Trie树：$O(\sum \text{单词长度})$。
  • 地图搜索：$O(n \times m \times 8^L)$（实际远低于理论值，因剪枝优化）。
• 空间复杂度：
  • Trie树存储：$O(26 \times \sum \text{单词长度})$。
  • 哈希表存储结果：$O(\text{唯一单词数量})$。

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>

#define WORD 26
#define MAXN 1050

using namespace std;

struct trie
{
	trie *child[WORD]; //儿子节点指针
	int id; //若该节点为某单词的终止节点,id=该单词编号
	trie(){
		memset(child,0,sizeof(child)); //儿子节点初始化为空
		id=-1;
	}
}; //root=根节点

trie *root=new trie();

int dx[]={-1,-1,0,1,1,1,0,-1};
int dy[]={0,1,1,1,0,-1,-1,-1}; //搜索方向，暴力枚举每一个点八个方向
int ans[MAXN][3],visit[MAXN],L,C,W; //第i个单词的位置=(ans[i][1],ans[i][2]),方向为ans[i][0]

string c[MAXN],word; //保存全部字符串的矩阵

void build(string s,int num) //将编号为num的字符串s插入trie树中
{
	int i;
	trie *p=root; //初始时p指向根节点
	for(i=0;i<s.size();i++)
	{
		if(p->child[s[i]-'A']==NULL) //无现成的字符串相应位置儿子节点
			p->child[s[i]-'A']=new trie();
		p=p->child[s[i]-'A']; //将指针移向当前节点以下的相应儿子节点
	}
	p->id=num; //记下终止节点的相应单词编号
}

void search(int sx,int sy,int dir) //搜索trie树,单词起点(sx,sy),延伸方向为dir
{
	int xx=sx,yy=sy; //当前单词字母的坐标(xx,yy)
	trie *point=root; //point指向当前trie树的节点
	while(xx>=0&&xx<L&&yy>=0&&yy<C) //坐标未越界
	{
		if(!point->child[c[xx][yy]-'A']) //到达了终止节点，但单词还没结束
			break;
		else
			point=point->child[c[xx][yy]-'A']; //指针向该节点下方移动
		if(point->id!=-1) //该节点为终止节点
		{
			if(visit[point->id]==0)
			{
				visit[point->id]=1;
				ans[point->id][0]=dir; //记录下该单词的開始坐标、方向
				ans[point->id][1]=sx;
				ans[point->id][2]=sy;
			}
		}
		xx+=dx[dir]; //移动坐标
		yy+=dy[dir];
	}
}

int main()
{
	int i,j,k;
	scanf("%d%d%d",&L,&C,&W);
	for(i=0;i<L;i++)
	{
		cin>>c[i];
	}
	for(i=0;i<W;i++)
	{
		cin>>word;
		build(word,i); //将单词插入trie树
	}
	for(i=0;i<L;i++) //枚举起点(i,j)
		for(j=0;j<C;j++)
			for(k=0;k<8;k++) //暴力枚举单词存在的方向
				search(i,j,k);
	for(i=0;i<W;i++)
		printf("%d %d %c\n",ans[i][1],ans[i][2],ans[i][0]+'A');
	return 0;
}