posts - 12,  comments - 10,  trackbacks - 0
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)  编辑 收藏 引用

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


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

常用链接

留言簿(3)

随笔档案

杭电!!

搜索

  •  

最新评论

阅读排行榜

评论排行榜