Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这题完全没必要用AC自动机

Posted by OZY123 at 2016-03-09 09:08:55 on Problem 1204
```一开始，看AC自动机题表是看到这题。。就以为是AC自动机，后来仔细一想，其实对于这题AC自动机几乎没有用，建一棵字典树，往裸图上跑就行了！接着，貌似没有相同的单词。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#define bid(x) {if (x>=N-1) x=1;}
const int N=10010;
const int root=0;
int dir[][2]={-1,0,-1,1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};//方向
char s[N][N];
char str[N];
int n,m,T;
struct qq
{
int c[30];
int s;
}t[N*30];int len;
struct qr
{
int x,y,z;
}ans[N];
void init(int x)
{
t[x].s=-1;
memset(t[x].c,-1,sizeof(t[x].c));
}
void bt (int num)
{
int x=root;
int len1=strlen(str);
for (int u=0;u<len1;u++)
{
int y=str[u]-'A';
if (t[x].c[y]==-1)
{
len++;
t[x].c[y]=len;
init(len);
}
x=t[x].c[y];
}
t[x].s=num;
return ;
}
int q[N];
int st,ed;
bool ok (int x,int y)
{
if (x>=0&&x<n&&y>=0&&y<m) return true;
return false;
}
void qs (int x,int y,int o)
{
int A=x,B=y;
int a=root;
while (ok(x,y)==true)
{
//printf("%d %d\n",x,y);
int b=(s[x][y]-'A');

if (t[a].c[b]==-1) return ;
/*printf("%d %d %d %d\n",x,y,b,a,t[a].c[b]);
system("pause");*/
a=t[a].c[b];
if (t[a].s!=-1)
{
int num=t[a].s;
ans[num].x=A;
ans[num].y=B;
ans[num].z=o;
}
x=x+dir[o][0];
y=y+dir[o][1];
}
return ;
}
void solve ()
{
for (int u=0;u<n;u++)
for (int i=0;i<m;i++)
for (int o=0;o<8;o++)
qs(u,i,o);
}
int main()
{
len=0;
scanf("%d%d%d",&n,&m,&T);
for (int u=0;u<n;u++)
scanf("%s",s[u]);
init(root);
for (int u=1;u<=T;u++)
{
scanf("%s",str);
bt(u);
}
solve();
for (int u=1;u<=T;u++)
printf("%d %d %C\n",ans[u].x,ans[u].y,(ans[u].z+'A'));
return 0;
}```

Followed by: