hdu 1501 Zipper

来源:互联网 时间:1970-01-01

一道搜索题,不过用了一个visit数组比较重要~~值得学习!!

题目大意:给3个字符串,问第三个串能不能由前两个构成,在不改变相互顺序的情况下!

visit标记数组很重要,去掉must超时~~

直接贴代码,代码很精简:

View Code
 1 # include<stdio.h>
2 # include<string.h>
3 char str1[205],str2[205],str[405],flag,visit[205][205];
4 void dfs(int i,int j,int k)
5 {
6 if(str[i]==0 && str1[j]==0 && str2[k]==0) {flag=1;return;}
7 if(str[i]!=str1[j] && str[i]!=str2[k]) return;
8 if(visit[j][k]) return;///如果该状态已经访问过了,那就无需再访问了
9 visit[j][k]=1;
10 if(str[i]==str1[j]) dfs(i+1,j+1,k);
11 if(flag) return;
12 if(str[i]==str2[k]) dfs(i+1,j,k+1);
13 }
14 int main()
15 {
16 int t,ncase;
17 scanf("%d",&ncase);
18 for(t=1;t<=ncase;t++)
19 {
20 scanf("%s%s%s",str1,str2,str);
21 memset(visit,0,sizeof(visit));
22 flag=0;
23 dfs(0,0,0);
24 printf("Data set %d: ",t);
25 if(flag) printf("yes/n");
26 else printf("no/n");
27 }
28 return 0;
29 }


相关阅读:
Top