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

## 我表示将一个赋值语句给注释掉之后是WA（测试哪里会出现RE）,加上就是RE，我瞬间觉得我被质子给玩了，给个程序，哪天有人知道了什么，麻烦留个言

Posted by skykey at 2012-07-25 11:36:25 on Problem 1204
```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define M 1024
#define queue_size M<<8
char s[M][M];
char tmp[M];
int dir[][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int l,c,w;
int len[M];
typedef struct node
{
node* fail;
node* next[26];
int k;
node(){
fail=NULL;memset(next,0,sizeof(next));
}
}Trie;
Trie* q[queue_size];
struct result
{
int x,y,d;
}ans[M];
void insert(char *str,Trie* rt,int k)
{
int i=0,index;
Trie* p=rt;
while(str[i])
{
index=str[i]-'A';
if(p->next[index]==NULL)p->next[index]=new Trie();
p=p->next[index];
i++;
}
p->k=k;
}
void build_ac_automation(Trie* rt)
{
int i;
rt->fail=NULL;
{

Trie *p=NULL,*tmp=q[tail++];tail%=queue_size;
for(i=0;i<26;i++){
if(tmp->next[i]!=NULL){
if(tmp==rt)tmp->next[i]->fail=rt;
else{
p=tmp->fail;
while(p!=NULL){
if(p->next[i]!=NULL){
tmp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL)tmp->next[i]->fail=rt;
}
}
}

}
}
int legal(int x,int y)
{
if(x<0||x>=l)return 0;
if(y<0||y>=c)return 0;
return 1;
}

void acrun(int x,int y,int d,node*r)
{
int a;
Trie *tmp,*cur=r;

for(;legal(x,y);x+=dir[d][0],y+=dir[d][1]){
a=s[x][y]-'A';
while(!cur->next[a]&&cur!=r)
cur=cur->fail;
cur=cur->next[a];
if(cur==NULL) cur=r;
tmp=cur;

while(tmp!=r&&tmp->k!=-1){
/* ans[tmp->k].x=x-dir[d][0]*(len[tmp->k]-1);
ans[tmp->k].y=y-dir[d][1]*(len[tmp->k]-1);
ans[tmp->k].d=d; */
tmp->k=-1;
tmp=tmp->fail;
}
}
}
void acwork(Trie* rt)
{
int i;
for(i=0;i<c;i++){
acrun(0,i,3,rt);acrun(0,i,4,rt);acrun(0,i,5,rt);
acrun(l-1,i,1,rt);acrun(l-1,i,0,rt);acrun(l-1,i,7,rt);
}
for(i=0;i<l;i++){
acrun(i,0,1,rt);acrun(i,0,2,rt);acrun(i,0,3,rt);
acrun(i,c-1,6,rt);acrun(i,c-1,7,rt);acrun(i,c-1,5,rt);
}
return;

}
int main()
{
int i;
scanf("%d%d%d",&l,&c,&w);
for(i=0;i<l;i++)scanf("%s",s[i]);
Trie* root=new Trie();
for(i=1;i<=w;i++){
scanf("%s",tmp);
len[i]=strlen(tmp);
insert(tmp,root,i);
}
build_ac_automation(root);

acwork(root);
for(i=1;i<=w;i++)
printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].d+'A');
//system("pause");
return 0;
}

```

Followed by: