开始wa掉了,360行的代码找错真难受!!!居然是一个地方多减了一个1……
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;
#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)
#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a) for( int i = (a)-1 ; i >= 0 ; i --)
#define S64(a) scanf(in64,&a)
#define SS(a) scanf("%d",&a)
#define LL(a) ((a)<<1)
#define RR(a) (((a)<<1)+1)
#define pb push_back
#define CL(Q) while(!Q.empty())Q.pop()
#define MM(name,what) memset(name,what,sizeof(name))
#define read freopen("1204.in","r",stdin)
#define write freopen("out.txt","w",stdout)
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1001;
const int maxc = 26;
const int maxz = 1000001;
const int head = 0;
int n,m,w;
string sd[maxn];
string s[maxn];
struct zz
{
int to[26];
int fail;
int id;
}zx[maxz];
bool vis[maxz];
int use;
int fx[maxn];
int fy[maxn];
char cf[maxn];
int get()
{
use++;
zx[use].id = 0;
zx[use].fail = 0;
MM(zx[use].to,-1);
return use;
}
void ac();
void insert(int id,string& p)
{
int now = head;
int c;
for(int i=0;i<p.length();i++)
{
c = p[i] - 'A';
if(zx[now].to[c] == -1)
{
zx[now].to[c] = get();
now = zx[now].to[c];
}
else
{
now = zx[now].to[c];
}
}
zx[now].id = id;
return ;
}
void ac()
{
queue<int>q;
CL(q);
q.push(0);
int now,to,temp;
while(!q.empty())
{
now = q.front();
q.pop();
for(int i=0;i<maxc;i++)
{
if(zx[now].to[i]!=-1)
{
to = zx[now].to[i];
temp = now;
q.push(to);
while(temp)
{
temp = zx[temp].fail;
if(zx[temp].to[i] != -1)
{
zx[to].fail = zx[temp].to[i];
break;
}
}
}
}
}
return ;
}
void find(int x,int y,char fc,int now)
{
while(now && !vis[now])
{
vis[now] = true;
if(zx[now].id)
{
int id = zx[now].id;
int low = s[id].length()-1;
int nowx,nowy;
if(fc == 'C')
{
nowx = x;
nowy = y - low;
}
else if(fc == 'G')
{
nowx = x;
nowy = y + low;
}
else if(fc == 'A')
{
nowx = x + low;
nowy = y;
}
else if(fc == 'E')
{
nowx = x - low;
nowy = y;
}
else if(fc == 'B')
{
nowx = x + low;
nowy = y - low;
}
else if(fc == 'F')
{
nowx = x - low;
nowy = y + low;
}
else if(fc == 'D')
{
nowx = x - low;
nowy = y - low;
}
else if(fc == 'H')
{
nowx = x + low;
nowy = y + low;
}
fx[id] = nowx;
fy[id] = nowy;
cf[id] = fc;
}
now = zx[now].fail;
}
return ;
}
void ak(int x,int y,char fc,string& p)
{
int now=head;
int temp;
int c;
for(int i=0;i<p.length();i++)
{
c = p[i]-'A';
if(zx[now].to[c] != -1)
{
now = zx[now].to[c];
}
else
{
temp = now;
while(now)
{
now = zx[now].fail;
if(zx[now].to[c] != -1)
{
now = zx[now].to[c];
break;
}
}
zx[temp].to[c] = now;
}
if(fc == 'C')
{
find(x,y+i,fc,now);
}
else if(fc == 'G')
{
find(x,y-i,fc,now);
}
else if(fc == 'A')
{
find(x-i,y,fc,now);
}
else if(fc == 'E')
{
find(x+i,y,fc,now);
}
else if(fc == 'B')
{
find(x-i,y+i,fc,now);
}
else if(fc == 'F')
{
find(x+i,y-i,fc,now);
}
else if(fc == 'D')
{
find(x+i,y+i,fc,now);
}
else if(fc == 'H')
{
find(x-i,y-i,fc,now);
}
}
return ;
}
void start()
{
ac();
string temp;
char c;
for(int i=0;i<n;i++)
{
temp = sd[i];
c = 'C';
ak(i,0,c,temp);
reverse(temp.begin(),temp.end());
c = 'G';
ak(i,m-1,c,temp);
}
for(int j=0;j<m;j++)
{
temp = "";
for(int i=0;i<n;i++)
{
temp += sd[i][j];
}
c = 'E';
ak(0,j,c,temp);
c = 'A';
reverse(temp.begin(),temp.end());
ak(n-1,j,c,temp);
}
for(int i=0;i<n;i++)
{
temp = "";
for(int j=0;j<=i && j<m;j++)
{
temp += sd[i-j][j];
}
c = 'B';
ak(i,0,c,temp);
reverse(temp.begin(),temp.end());
c = 'F';
ak(i-min(m-1,i),min(m-1,i),c,temp);
}
for(int j=0;j<m;j++)
{
temp = "";
for(int i=n-1;i>=0 && j+n-1-i<=m-1;i--)
{
temp += sd[i][j+n-1-i];
}
c = 'B';
ak(n-1,j,c,temp);
reverse(temp.begin(),temp.end());
c = 'F';
ak(max(0,j+n-m),j+n-1-max(0,j+n-m),c,temp);
}
for(int i=0;i<n;i++)
{
temp = "";
for(int j=0;j<=n-1-i && j<m ;j++)
{
temp += sd[i+j][j];
}
c = 'D';
ak(i,0,c,temp);
reverse(temp.begin(),temp.end());
c = 'H';
ak(i+min(n-1-i,m-1),min(n-1-i,m-1),c,temp);
}
for(int j=0;j<m;j++)
{
temp = "";
for(int i=0;i<n && j+i<m;i++)
{
temp += sd[i][j+i];
}
c = 'D';
ak(0,j,c,temp);
reverse(temp.begin(),temp.end());
c = 'H';
ak(min(n-1,m-j-1),j+min(n-1,m-j-1),c,temp);
}
return ;
}
int main()
{
cin>>n>>m>>w;
use = -1;
get();
MM(vis,false);
for(int i=0;i<n;i++)
{
cin>>sd[i];
}
for(int i=1;i<=w;i++)
{
cin>>s[i];
insert(i,s[i]);
}
start();
for(int i=1;i<=w;i++)
{
cout<<fx[i]<<" "<<fy[i]<<" "<<cf[i]<<endl;
}
return 0;
}
分享到:
相关推荐
poj1007 AC代码 0MS过题写法 不过是个水题 哈哈哈哈
poj 3674 SuperAssassin 的AC代码
我的Poj里的一些AC代码
poj3586,推导题,可以推导出一个贪心的结论,具体看代码。
poj2342,树形dp,dp[i][0]表示i不参加party,其下属(包括非直接下属)能得到的最优值。dp[i][1]表示i参加的其下属和他能得到的最优值。
http://acm.pku.edu.cn/JudgeOnline/ acm的AC解题报告
一年多的ACM经历,做了这300多题,希望对大家有帮助!!
poj2343,规模比较小,只有50,搜索即可,具体看代码。
POJ 1328 java做!雷达问题!java版本!AC答案~
复杂度n^2 b
poj2628,判断需要锯掉多少长度才能使得桌子平衡,可以知道至少需要三根相同长度且是最长的桌腿。按桌腿长度排序,然后判断是否可以保持平衡(所有桌腿不同在圆心的一边即可)
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
poj2340,模拟题,使用两个优先队列模拟即可。
poj2605,简单推导题。分几种情况讨论即可。
poj2599,简单dfs可以过此题,按顺序搜到任意可行解即可。
北大poj AC源码1600个(C或C++)
1000 1003 1004 1005 1006 1008 1012 1028 1036 1045 1046 1047 1087 1163 1183 1207 1218 1247 1269 1298 1306 1316 1326 1331 1338 1401 1423 1450 1455 1477 1488 1503 1504 1517 1519 1528 1543 1547 1552 1555 ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
解决poj1006问题
用栈来解决。设置两个数组,其中一个是要求输入的数组a。另一个数组b用于保存含有相同的元素的序列。 先把数组的第一个值压入栈底,在看第二个数是不是和第一个数是相同的。如果相同则进栈,否则的话栈底元素出栈...