PKU 1204

#include<cstdio> 
#include<cstring>
#define maxn 200010
using namespace std;
bool vis[26];
int n,m,w,x,y,sz=1;//sz得为全局变量 
char str[1010][1010],word[1010];
int val[maxn],out[1010][3];
int dir[8][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};//顺时针 
struct Trie
{
    int next[26];
}trie[maxn];

void insert(char *s,int k)
{
    int u=0,len=strlen(s);
    for(int i=0;i<len;i++){
        int id=s[i]-‘A‘;
        if(!trie[u].next[id]) 
            trie[u].next[id]=sz++;
        u=trie[u].next[id];
    }
    val[u]=k;//u为结点编号,k为单词编号 
}
void dfs(int u,int i,int j,int k)//k记录方向 
{
    if(u==0||i<0||i>=n||j<0||j>=m) return;//该语句之前放在if(val[u])条件之后,WA
    if(val[u]){
        out[val[u]][0]=x;
        out[val[u]][1]=y;
        out[val[u]][2]=k;
        val[u]=0;//做标记,因为不查询重复单词 
    }
    int id=str[i+dir[k][0]][j+dir[k][1]]-‘A‘;
    dfs(trie[u].next[id],i+dir[k][0],j+dir[k][1],k);//必须得朝同一方向搜索 
}

int main()
{
    scanf("%d%d%d",&n,&m,&w);
    for(int i=0;i<n;i++)
        scanf("%s",str[i]);
    for(int i=1;i<=w;i++){
        scanf("%s",word);
        insert(word,i);
        vis[word[0]-‘A‘]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[str[i][j]-‘A‘]){ 
                for(int k=0;k<8;k++){
                    x=i,y=j;//记录下最初的位置,从Trie树根开始向下搜索 
                    dfs(trie[0].next[str[i][j]-‘A‘],i,j,k);
                }
            } 
        }
    }
    for(int i=1;i<=w;i++)
        printf("%d %d %c\n",out[i][0],out[i][1],out[i][2]+‘A‘);
    return 0;
}