【分析】
听说TRIE+爆搜能过,于是我就爆搜了。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxl 1010 char s[Maxl][Maxl];
char ss[Maxl][Maxl];
int dx[]={,,,,-,-,-,,},
dy[]={,,-,-,-,,,,};
int ans[Maxn][],dr[Maxn];
int n,m; struct node
{
int son[],cnt,fail;
int num,rt,p;
}t[Maxn*];int tot; void upd(int x)
{
t[x].cnt=;t[x].p=;
memset(t[x].son,,sizeof(t[x].son));
} void read_trie(int x)
{
scanf("%s",ss[x]+);
int len=strlen(ss[x]+);
int now=;
for(int j=;j<=len;j++) ss[][j]=ss[x][len-j+];
for(int j=;j<=len;j++)
{
int ind=ss[][j]-'A'+;
if(!t[now].son[ind])
t[now].son[ind]=++tot,upd(tot);
now=t[now].son[ind];
if(j==len) t[now].cnt++,t[now].p=x;
}
} void dfs(int x,int y,int dir,int now)
{
if(t[now].p!=)
{
int q=t[now].p;
ans[q][]=x;ans[q][]=y;dr[q]=dir;
t[now].p=;
}
if(x+dx[dir]<||x+dx[dir]>n||y+dy[dir]<||y+dy[dir]>m) return;
int a=t[now].son[s[x+dx[dir]][y+dy[dir]]-'A'+];
if(a!=)
dfs(x+dx[dir],y+dy[dir],dir,a);
} void init()
{
int q;
scanf("%d%d%d",&n,&m,&q);
for(int i=;i<=n;i++)
{
scanf("%s",s[i]+);
}
tot=;upd();
for(int i=;i<=q;i++)
{
read_trie(i);
}
for(int i=;i<=n+;i++)
for(int j=;j<=m+;j++)
{
for(int k=;k<=;k++)
{
dfs(i,j,k,);
}
}
for(int i=;i<=q;i++)
{
printf("%d %d %c\n",ans[i][]-,ans[i][]-,dr[i]+'A'-);
}
} int main()
{
init();
return ;
}
[POJ1204]
2016-06-19 14:09:06
后来还是打了一下AC自动机,嗯,感觉for那里还是超级慢,因为重叠那部分不好搞,就这样吧。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 1010
#define Maxl 1010 char s[Maxl][Maxl];
char ss[Maxl][Maxl];
int dx[]={,,,,-,-,-,,},
dy[]={,,-,-,-,,,,};
int ans[Maxn][],dr[Maxn];
int n,m,qy; struct node
{
int son[],cnt,fail;
int num,rt;
}t[Maxn*];int tot; int p[Maxn]; void upd(int x)
{
t[x].cnt=;/*t[x].p=0;*/
memset(t[x].son,,sizeof(t[x].son));
} void read_trie(int x)
{
scanf("%s",ss[x]+);
int len=strlen(ss[x]+);
int now=;
for(int j=;j<=len;j++) ss[][j]=ss[x][len-j+];
for(int j=;j<=len;j++)
{
int ind=ss[][j]-'A'+;
if(!t[now].son[ind])
t[now].son[ind]=++tot,upd(tot);
now=t[now].son[ind];
if(j==len) t[now].cnt++,p[x]=now;
}
} queue<int > q;
void build_AC()
{
int i,j,x,y;
while(!q.empty()) q.pop();
q.push();
while(!q.empty())
{
x=q.front();
y=t[x].fail;
for(j=;j<=;j++)
{
if(t[x].son[j])
{
q.push(t[x].son[j]);
t[t[x].son[j]].fail=x?t[y].son[j]:x;
}
else t[x].son[j]=t[y].son[j];
}
q.pop();
}
} void check(int x,int y,int dir,int now)
{
if(now==) return;
for(int i=;i<=qy;i++) if(p[i]==now)
{
ans[i][]=x;
ans[i][]=y;
dr[i]=dir;
}
now=t[now].fail;
check(x,y,dir,now);
} void dfs(int x,int y,int dir,int now)
{
now=t[now].son[s[x][y]-'A'+];
check(x,y,dir,now);
x=x+dx[dir],y=y+dy[dir];
if(x<||x>n||y<||y>m) return;
dfs(x,y,dir,now); } void init()
{
scanf("%d%d%d",&n,&m,&qy);
for(int i=;i<=n;i++)
{
scanf("%s",s[i]+);
}
tot=;upd();
for(int i=;i<=qy;i++)
{
read_trie(i);
}
build_AC();
for(int i=;i<=n;i++)
for(int k=;k<=;k++)
{
dfs(i,,k,);
dfs(i,m,k,);
}
for(int j=;j<=m;j++)
for(int k=;k<=;k++)
{
dfs(,j,k,);
dfs(n,j,k,);
}
for(int i=;i<=qy;i++)
{
printf("%d %d %c\n",ans[i][]-,ans[i][]-,dr[i]+'A'-);
}
} int main()
{
init();
return ;
}
[POJ1204-2]
2016-06-21 17:14:17