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

为毛C++AC而G++RE呢?而且把gets换成scanf答案会错?

Posted by Fri_Gazer at 2014-05-07 16:24:47 on Problem 1204
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator