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