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 閱讀(494)
評論(0) 編輯 收藏 引用