POJ1204 WORD PUZZLES

Description

给定一个行列的、由大写字母构成的矩阵，以及个单词。每个单词可在矩阵中的任何位置朝着任何方向出现，且仅出现一次。编程找出每个单词的首字母在矩阵中的位置，以及单词的朝向。

Input Format

第一行为一个整数T，表示数据的组数。下面有T组数据。每组数据中：
第行为三个不超过1000的整数。
下面行，每行个大写字母，表示矩阵。
下面行，每行一个单词。

Output Format

对每组数据，输出行，每行为两个整数和一个字母，用一个空格隔开。第行的两个整数表示第个单词首字母的行号和列号（从上至下依次为第至行，从左往右依次为第至列）；字母表示单词的朝向，对应关系如下：

Sample Input

1
4 5 4
MAIGO
QKRPT
AREMO
WERTY
AKI
MAIGO
ARM
ARMY

Sample Output

2 0 B
0 0 C
0 0 A
0 1 D

Constraints

如题。

CCYOS

这是一道AC自动机。
由于数据比较小，所以可以暴力做。
不用枚举矩阵中的每个点作为文本串的起点，枚举矩阵边缘和从这个边缘可以拓展的方向。
code

//#include<bits/stdc++.h>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

int L,C,W,cnt;
struct str{
    char a[1005];
}in[1005];
int cx[8] = {-1,-1,0,1,1,1,0,-1};
int cy[8] = {0,1,1,1,0,-1,-1,-1};
int ch[1000005][26],ed[1000005],nxt[1000005],dan[1000005];
struct Ans{
    int x,y,dir;
}ans[1005];

inline void build(char* s,int id){
    int now = 0,len =strlen(s);
    for(int i = len - 1;i >= 0;--i){
        int c = s[i] - 'A';
        if(!ch[now][c])ch[now][c] = ++cnt;
        now =ch[now][c];
    }
    ed[now] = id;
}

inline void get_nxt(){
    int now = 0;
    queue<int> q;while(q.size())q.pop();
    for(int i = 0;i < 26;++i)if(ch[0][i])q.push(ch[0][i]);
    while(q.size()){
        now = q.front();q.pop();
        for(int i = 0;i < 26;++i){
            if(ch[now][i]){
                nxt[ch[now][i]] = ch[nxt[now]][i];q.push(ch[now][i]);
    //          if(ed[ch[now][i]])dan[ch[now][i]] = ch[now][i];
    //          else dan[ch[now][i]] = dan[nxt[ch[now][i]]];
            }
            else ch[now][i] = ch[nxt[now]][i];
        }
    }
}

inline void ask(int x,int y,int dir){
    int now = 0;
    while(x < L&&y < C&&x >= 0&&y >= 0){
        now = ch[now][in[x].a[y] - 'A'];
    //  for(int t = now;t;t = nxt[t]){
            if(ed[now]){
                ans[ed[now]].x = x;
                ans[ed[now]].y = y;
                ans[ed[now]].dir = (dir + 4)%8;
    //      }
        }
        x += cx[dir];y += cy[dir];
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&L,&C,&W);
        for(int i = 0;i < L;++i)scanf("%s",in[i].a);
        for(int i = 1;i <= W;++i){
            scanf("%s",in[L].a);
            build(in[L].a,i);
        }
        get_nxt();
        for(int i = 0;i < L;++i)ask(i,0,2),ask(i,C - 1,6),ask(i,0,1),ask(i,0,3),ask(i,C - 1,7),ask(i,C - 1,5);
        for(int i = 0;i < C;++i)ask(0,i,4),ask(0,i,3),ask(0,i,5),ask(L - 1,i,0),ask(L - 1,i,1),ask(L - 1,i,7);

        for(int i = 1;i <= W;++i)
            printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].dir + 'A');
        memset(nxt,0,sizeof nxt);
        memset(ch,0,sizeof ch);
    }
    return 0;
}