posts - 33,  comments - 25,  trackbacks - 0
DFS+剪枝.剪枝主要是判断现有输出是否与最终期望字符串前缀匹配.
Code
posted on 2009-03-24 20:45 肖羽思 阅读(1901) 评论(2)  编辑 收藏 引用 所属分类: ZOJ

FeedBack:
# re: ZOJ 1004 解题报告
2009-05-08 20:55 | D
D  回复  更多评论
  
# re: ZOJ 1004 解题报告
2009-09-24 18:04 | bloodmoon
@D
为什么写了这么长
#include <stdio.h>
#include <string.h>
char s1[100],s2[100],stk[100],ans[200];
int l1,l2;

void output(int n)
{
int i;
for(i=0;i+1<n;i++)
{
printf("%c ",ans[i]);
}
printf("%c\n",ans[i]);
}

void go(int in,int out,int p,int top)
{
if(top<0)return;
if(in==l1 && out==l2)
{
output(p);
return;
}

if(in<l1)
{
stk[top]=s1[in];
ans[p]='i';
go(in+1,out,p+1,top+1);
}

if(top>0 && out<l2 && stk[top-1]==s2[out])
{
ans[p]='o';
go(in,out+1,p+1,top-1);
stk[top-1]=s2[out];
}
}

int main()
{
FILE * fp;
fp = fopen("1004.in","r");
while(fscanf(fp,"%s%s",s1,s2)==2)
{
l1=strlen(s1);
l2=strlen(s2);
printf("[\n");
if(l1==l2)go(0,0,0,0);
printf("]\n");
}
return 0;
}  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2009年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿(3)

随笔分类

随笔档案

文章分类

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜