| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
为毛C++AC而G++RE呢?而且把gets换成scanf答案会错?#include <cstdio>
#include <cstring>
using namespace std;
const int dx[8] = {-1,-1,0,1,1,1,0,-1};
const int dy[8] = {0,1,1,1,0,-1,-1,-1};
const char com[8] = {'A','B','C','D','E','F','G','H'};
const int N = 2010;
const int M = 1000000;
int tire[M][26],sz,len[N],gy[M],FF_Sky[M],q[M],next[M],last[M],u,n,m,t,ansx[N],ansy[N],ans[N];
char s[N][N];
void _insert(char *s,int k){
int now,i;
for (now = i = 0; i < len[k]; i++){
u = s[i]-'A';
if (!tire[now][u]){
tire[now][u] = ++sz;
}
now = tire[now][u];
}
FF_Sky[now]++;
gy[now] = k;
}
void getfail(){
int l,r,i,x,v;
l = 1; r = 0;
for (i = 0; i < 26; i++) if (tire[0][i]) q[++r] = tire[0][i],last[tire[0][i]] = 0;
while (l <= r){
x = q[l]; l++;
for (i = 0; i < 26; i++){
if (!tire[x][i]){
tire[x][i] = tire[next[x]][i];
continue;
}
u = tire[x][i];
q[++r] = u;
v = next[x];
next[u] = tire[v][i];
last[u] = FF_Sky[next[u]]? next[u]:last[next[u]];
}
}
}
void work(){
int i,now,temp,sum,x,y;
sum = 0;
for (i = 0; i < n; i++){
now = 0;
for (y = 0; y < m; y++){
u = s[i][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = i;
ansy[gy[temp]] = y;
ans[gy[temp]] = 2;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (y = m-1; y > -1; y--){
u = s[i][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = i;
ansy[gy[temp]] = y;
ans[gy[temp]] = 6;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = i,y = 0; x < n && y < m; x++,y++){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 3;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = i,y = 0; x > -1 && y < m; x--,y++){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 1;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = i,y = m-1; x > -1,y > -1; x--,y--){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 7;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = i,y = m-1; x < n,y > -1; x++,y--){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 5;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
}
for (i = 0; i < m; i++){
now = 0;
for (x = 0; x < n; x++){
u = s[x][i]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = i;
ans[gy[temp]] = 4;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = n-1; x > -1; x--){
u = s[x][i]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = i;
ans[gy[temp]] = 0;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = 0,y = i; x < n,y < m; x++,y++){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 3;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = 0,y = i; x < n,y > -1; x++,y--){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 5;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = n-1,y = i; x > -1 && y > -1; x--,y--){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 7;
sum++;
}
temp = last[temp];
}
}
if (sum == t) return;
now = 0;
for (x = n-1,y = i; x > -1 && y > -1; x--,y++){
u = s[x][y]-'A';
now = tire[now][u];
if (FF_Sky[now]) temp = now;
else temp = last[now];
while (temp){
if (ans[gy[temp]] == -1){
ansx[gy[temp]] = x;
ansy[gy[temp]] = y;
ans[gy[temp]] = 1;
sum++;
}
temp = last[temp];
}
}
}
}
int main(){
int i;
char st[N];
scanf("%d%d%d",&n, &m, &t); getchar();
for (i = 0; i < n; i++) gets(s[i]);
for (i = 0; i < t; i++){
gets(st);
len[i] = strlen(st);
_insert(st,i);
}
getfail();
for (i = 0; i < t; i++) ans[i] = -1;
work();
for (i = 0; i < t; i++){
printf("%d %d %c\n", ansx[i]-dx[ans[i]]*(len[i]-1), ansy[i]-dy[ans[i]]*(len[i]-1), com[ans[i]]);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator