http://acm.hdu.edu.cn/showproblem.php?pid=1501第一次接触所搜,在学长的帮助之下终于AC了!虽然不是自己独立完成的,但是至少对搜索有了感性认识!!好的开始啊!!O(∩_∩)O~
#include<stdio.h>
char a[1001],b[1001],c[2002];
long lena,lenb,lenc,d[1001][1001],q;//d[1001][1001]用于剪枝,标记是否操作过,=1是,=0否
int LS(long i,long j,long k)
{
if(lenc-1==k){
q=1;
return 0;}
if(d[i][j]==1)return 0;
d[i][j]=1;
if(q==1||a[i]!=c[k]&&b[j]!=c[k])return 0;
if(i<lena&&a[i]==c[k])
LS(i+1,j,k+1);
if(j<lenb&&b[j]==c[k])
LS(i,j+1,k+1);
}
int main()
{
long i,j,n,m,ri;
scanf("%d",&n);
getchar();
for(ri=1;ri<=n;ri++){
scanf("%s%s%s",a,b,c);
q=0;
lena=strlen(a);
lenb=strlen(b);
lenc=strlen(c);
for(i=0;i<=lena;i++)
for(j=0;j<=lenb;j++)
d[i][j]=0;
LS(0,0,0);
if(q==1)printf("Data set %d: yes\n",ri);
else printf("Data set %d: no\n",ri);
}
}
posted on 2009-04-17 17:57
zhoubaozhong 阅读(476)
评论(0) 编辑 收藏 引用